Name: Markov Decision Processes
ISBN: 9780471727828

Markov Decision Processes

The past decade has seen considerable theoretical and applied research on Markov decision processes, as well as the growing use of these models in ecology, economics, communications engineering, and other fields where outcomes are uncertain and sequential decision-making processes are needed. A timely response to this increased activity, Martin L. Puterman's new work provides a uniquely up-to-date, unified, and rigorous treatment of the theoretical, computational, and applied research on Markov decision process models. It discusses all major research directions in the field, highlights many significant applications of Markov decision processes models, and explores numerous important topics that have previously been neglected or given cursory coverage in the literature. Markov Decision Processes focuses primarily on infinite horizon discrete time models and models with discrete time spaces while also examining models with arbitrary state spaces, finite horizon models, and continuous-time discrete state models. The book is organized around optimality criteria, using a common framework centered on the optimality (Bellman) equation for presenting results. The results are presented in a "theorem-proof" format and elaborated on through both discussion and examples, including results that are not available in any other book. A two-state Markov decision process model, presented in Chapter 3, is analyzed repeatedly throughout the book and demonstrates many results and algorithms.

What Hacker News says

blahblahblah10Aug 2020

I would highly recommend Sergey Levine's course:

http://rail.eecs.berkeley.edu/deeprlcourse/

For a more mathematical treatment, there's a beautiful book by Puterman:

https://www.amazon.com/Markov-Decision-Processes-Stochastic-...

thread

verdatelAug 2011

The theory of multi-armed bandits arises from the study of Markov decision processes (MDP). This field is also closely studied in and related to Stochastic Control and Dynamic Programming. A good book on MDP's is "Markov Decision Processes: Discrete Stochastic Dynamic Programming by Martin Puterman". It's fairly mathematical and is for grad-level learning. An alternative is another superb book "Dynamic Programming and Optimal Control" by Dimitri Bersekas.

A more accessible book is "Approximate Dynamic Programming" by Warren Powell.

I'm not sure if you know what a Markov chain is? Very roughly, any kind of data which changes its value (sometimes referred to as "state") and jumps to a new value is a Markov chain. The value that the chain jumps to is determined probabilistically using some distribution over all the states. When there are several Markov chains in parallel and each of them contribute to a certain reward and we are faced with the problem of which Markov chain to "control" or influence.. then it becomes a multi-armed bandit problem. They are not very easy to solve, except when certain simplifying assumptions are made. You can get a good start by looking at some MATLAB code from Prof. Kevin Murphy at UBC : http://www.cs.ubc.ca/~murphyk/Software/MDP/mdp.html

thread

cbarrickMay 2025

You should read more about Markov Decision Processes (MDPs) and Game Theory in general.

The word "solve" is well defined in this context, and is used accurately by OP. You "solve" a game by finding the policy that maximizes the expected return.

Obviously we can only talk about "expectation" because the outcome is random. But that doesn't mean that an optimal policy doesn't exist.

Optimal policies are also often random, expressed like "in state S, perform action A with probability P and action B with probability 1-P". A policy then boils down to a table, with a row for each state and a column for each action, where each cell is the probability of performing that action in that state.

Even more interesting are partially observable Markov decision processes, where your agent doesn't even know what state it is in. Instead, you get observations that hint to the true state, and you model the state as a probability distribution over possible concrete states. Solving these POMDPs is quite a bit more difficult than traditional MDPs.

It is possible to solve some MDPs (and POMDPs) by hand, but in practice we often use reinforcement learning to learn the policy table by simulating games.

thread