A Markov decision process (MDP) is a mathematical model for sequential decision making when outcomes are uncertain. It is a type of stochastic decision process, and is often solved using the methods of stochastic dynamic programming.
Originating from operations research in the 1950s, MDPs have since gained recognition in a variety of fields, including ecology, economics, healthcare, telecommunications and reinforcement learning. Reinforcement learning utilizes the MDP framework to model the interaction between a learning agent and its environment. In this framework, the interaction is characterized by states, actions, and rewards. The MDP framework is designed to provide a simplified representation of key elements of artificial intelligence challenges. This modeling framework incorporates the understanding of cause and effect, the management of uncertainty and nondeterminism, and the pursuit of explicit goals.
The name comes from its connection to Markov chains, a concept developed by the Russian mathematician Andrey Markov. The "Markov" in "Markov decision process" refers to the underlying structure of state transitions that still follow the Markov property. The process is called a "decision process" because it involves making decisions that influence these state transitions, extending the concept of a Markov chain into the realm of decision-making under uncertainty.
Definition
A Markov decision process is a 4-tuple , where:
is a set of states called the state space. The state space may be discrete or continuous, like the set of real numbers. is a set of actions called the action space (alternatively, is the set of actions available from state ). As for state, this set may be discrete or continuous. is the probability that action in state at time will lead to state at time . In general, this probability transition is defined to satisfy for every measurable. In case the state space is discrete, the integral is intended with respect to the counting measure, so that the latter simplifies as ; in case , the integral is usually intended with respect to the Lebesgue measure. is the immediate reward (or expected immediate reward) received after action is taken to transition from state to state . The reward is in general a random variable.
A policy function is a (potentially probabilistic) mapping from state space () to action space ().
Optimization objective
The goal in a Markov decision process is to find a good "policy" for the decision maker: a function that specifies the action that the decision maker will choose when in state . Once a Markov decision process is combined with a policy in this way, this fixes the action for each state and the resulting combination behaves like a Markov chain (since the action chosen in state is completely determined by ).
The objective is to choose a policy that will maximize some cumulative function of the random rewards, typically the expected discounted sum over a potentially infinite horizon:
(where we choose , i.e. actions given by the policy). And the expectation is taken over
where is the discount factor satisfying , which is usually close to (for example, for some discount rate ). A lower discount factor makes the decision maker more short-sighted, in that it comparatively disregards the effect that following its current policy has at times lying further in the future.
Another possible, but strictly related, objective that is commonly used is the step return. This time, instead of using a discount factor , the agent is interested only in the first steps of the process, with each reward having the same weight.
(where we choose , i.e. actions given by the policy). And the expectation is taken over
where is the time horizon. Compared to the previous objective, the latter one is more used in Learning Theory.
A policy that maximizes the function above is called an optimal policy and is usually denoted . A particular MDP may have multiple distinct optimal policies. Because of the Markov property, it can be shown that the optimal policy is a function of the current state, as assumed above. When is deterministic, there will always exist an optimal policy which is deterministic as well.
Assume that is deterministic, meaning for constants the value is also constant. For it is known that there exists a unique fixed point which satisfies the value iteration (Bellman equation) recursion
From inspection, notice that this fixed point is the value function associated to the following policy.
By unrolling the Bellman recursion, one can show that is indeed optimal (simultaneously for all states) over the set of deterministic policies.
Consider the case where is probabilistic, meaning the action taken is a random variable. One can show any such non-deterministic policy is dominated by deterministic as follows.
Simulator models
In many cases, it is difficult to represent the transition probability distributions, , explicitly. In such cases, a simulator can be used to model the MDP implicitly by providing samples from the transition distributions. One common form of implicit MDP model is an episodic environment simulator that can be started from an initial state and yields a subsequent state and reward every time it receives an action input. In this manner, trajectories of states, actions, and rewards, often called episodes may be produced.
Another form of simulator is a generative model, a single step simulator that can generate samples of the next state and reward given any state and action. (Note that this is a different meaning from the term generative model in the context of statistical classification.) In algorithms that are expressed using pseudocode, is often used to represent a generative model. For example, the expression might denote the action of sampling from the generative model where and are the current state and action, and and are the new state and reward. Compared to an episodic simulator, a generative model has the advantage that it can yield data from any state, not only those encountered in a trajectory.
These model classes form a hierarchy of information content: an explicit model trivially yields a generative model through sampling from the distributions, and repeated application of a generative model yields an episodic simulator. In the opposite direction, it is only possible to learn approximate models through regression. The type of model available for a particular MDP plays a significant role in determining which solution algorithms are appropriate. For example, the dynamic programming algorithms described in the next section require an explicit model, and Monte Carlo tree search requires a generative model (or an episodic simulator that can be copied at any state), whereas most reinforcement learning algorithms require only an episodic simulator.
Example
An example of MDP is the Pole-Balancing model, which comes from classic control theory.
In this example, we have
is the set of ordered tuples given by pole angle, angular velocity, position of the cart and its speed. is , corresponding to applying a force on the left (right) on the cart. is the transition of the system, which in this case is going to be deterministic and driven by the laws of mechanics. is if the pole is up after the transition, zero otherwise. Therefore, this function only depend on in this specific case.
Algorithms
Solutions for MDPs with finite state and action spaces may be found through a variety of methods such as dynamic programming. The algorithms in this section apply to MDPs with finite state and action spaces and explicitly given transition probabilities and reward functions, but the basic concepts may be extended to handle other problem classes, for example using function approximation. Also, some processes with countably infinite state and action spaces can be exactly reduced to ones with finite state and action spaces.
The standard family of algorithms to calculate optimal policies for finite state and action MDPs requires storage for two arrays indexed by state: value , which contains real values, and policy , which contains actions. At the end of the algorithm, will contain the solution and will contain the discounted sum of the rewards to be earned (on average) by following that solution from state .
The algorithm has two steps, (1) a value update and (2) a policy update, which are repeated in some order for all the states until no further changes take place. Both recursively update a new estimation of the optimal policy and state value using an older estimation of those values.
Their order depends on the variant of the algorithm; one can also do them for all states at once or state by state, and more often to some states than others. As long as no state is permanently excluded from either of the steps, the algorithm will eventually arrive at the correct solution.
Notable variants
Value iteration In value iteration , which is also called backward induction, the function is not used; instead, the value of is calculated within whenever it is needed. Substituting the calculation of into the calculation of gives the combined step;
where is the iteration number. Value iteration starts at and as a guess of the value function. It then iterates, repeatedly computing for all states , until converges with the left-hand side equal to the right-hand side (which is the "Bellman equation" for this problem). Lloyd Shapley's 1953 paper on stochastic games included as a special case the value iteration method for MDPs, but this was recognized only later on.
Value iteration is guaranteed to converge for by the Banach fixed-point theorem.
The Banach fixed-point theorem states that a given contraction mapping has a unique fixed point; further, one can asymptotically approach this fixed points by iterated application of the contraction mapping. It then suffices to show that value iteration is a contraction mapping, which is shown below for .
Denote and for convenience.
Policy iteration In policy iteration, one first performs Value Determination by solving for from the linear system described in step one, then performs Policy Improvement by computing as in step two, then repeats both steps until the policy converges. (Policy iteration was invented by Howard to optimize Sears catalogue mailing, which he had been optimizing using value iteration.Howard 2002, "Comments on the Origin and Application of Markov Decision Processes")
Since policy iteration effectively interleaves a linear inverse problem with a nonlinear operation, it may interpreted as a type of relaxation method.
This variant has the advantage that there is a definite stopping condition. Since there is a unique solution for each policy , the algorithm is completed once the Policy Improvement produces the same policy twice consecutively.
While there are situations where policy iteration may be faster than value iteration (e.g. when the action space is significantly larger than the state space), policy iteration is usually slower than value iteration for a large number of possible states.
Modified policy iteration In modified policy iteration (; ), step one is repeated several times, and then step two is performed once. Then step one is again repeated several times and so on.
Prioritized sweeping In this variant, the steps are preferentially applied to states which are in some way important – whether based on the algorithm (there were large changes in or around those states recently) or based on use (those states are near the starting state, or otherwise of interest to the person or program using the algorithm).
Computational complexity