Markov Decision Processes

A Markov chain drifts along on its own — you watch, you cannot steer. But most real systems come with a steering wheel: a maintenance engineer chooses when to service a machine, a warehouse chooses when to reorder, a robot chooses which way to move. Add decisions and rewards to a Markov chain and you get a Markov decision process (MDP) — the master framework for making a sequence of choices under uncertainty. It is where dynamic programming, stochastic modelling and, ultimately, reinforcement learning all meet.

The four ingredients

An MDP is specified by four things:

States s \in S — the situations the system can be in (machine working or broken, robot's grid cell, inventory level).
Actions a \in A(s) — the choices available in each state (run or maintain, move north/south, order or wait).
Transition probabilities P(s' \mid s, a) — the chance of landing in state s' after taking action a in state s. The Markov property holds: these depend only on the current state and action.
Rewards R(s, a) — the immediate payoff (or negative cost) for that action.

The randomness comes from P; the control comes from choosing a. Compared with an ordinary Markov chain, the single new element is that we pick the action that shapes the transition.

Policies and value

A policy \pi is a rule that assigns an action to every state — a complete "if in this situation, do that" strategy. Fix a policy and the MDP becomes a plain Markov chain that rolls forward, collecting rewards. We compare policies by the value function V^{\pi}(s): the total reward we expect to accumulate starting from state s and following \pi ever after.

Because rewards stretch into the infinite future, we discount them by a factor 0 \le \gamma < 1 per step, so a reward k steps away is worth \gamma^{k} of its face value. Discounting keeps the infinite sum finite and captures the intuition that sooner is better than later.

The Bellman optimality equation

The prize is the optimal value function V^{*}(s) — the best expected discounted reward achievable from s under any policy. It satisfies the Bellman optimality equation, the central identity of the whole subject:

V^{*}(s) = \max_{a \in A(s)} \left\{\, R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V^{*}(s') \,\right\}.

Read it aloud: the best value here is the best over actions of the immediate reward plus the discounted expected value of wherever you land. It is the principle of optimality again, now with a max over actions and an expectation over random outcomes baked in. The optimal policy simply picks, in each state, the action that attains the maximum.

Two ways to solve it

The Bellman equation is a fixed-point condition, and there are two classic iterative solvers:

Value iteration — start with a guess of V and repeatedly apply the Bellman update (the right-hand side as an assignment). Each sweep pulls the estimate closer to V^{*}; the discount \gamma makes it a contraction, so it converges geometrically.
Policy iteration — alternate evaluating the current policy (solve for its value) and improving it (act greedily with respect to that value). It converges in a finite number of policy changes, often just a handful.

Value iteration takes many cheap steps; policy iteration takes few expensive ones. Both march to the same optimal policy. The curve below shows a value estimate climbing to its true value under repeated Bellman updates — each iteration closes a fixed fraction \gamma of the remaining gap:

A one-step backup

Suppose in some state you may take action a with immediate reward R = 5, and it leads (for simplicity, deterministically) to a state whose optimal value is 10, with discount \gamma = 0.9. The value of that action is 5 + 0.9 \times 10 = 14. Do this for every action and keep the largest — that single number is the Bellman backup, the atom out of which value iteration is built.

The factor \gamma does double duty. Economically it is a discount rate — a pound today beats a pound next year, so future rewards are shrunk. But \gamma also has a neat probabilistic reading: a discounted infinite-horizon problem is equivalent to an undiscounted one in which the process randomly terminates each step with probability 1 - \gamma. A discount of \gamma = 0.9 is like playing a game that has a 10% chance of ending after every move — which is why nearer rewards, more likely to actually be collected, count for more.

Everything here rests on two assumptions that are easy to forget. First, the Markov property: the transition probabilities must depend only on the current state and action — if the true dynamics secretly depend on unseen history, the state is mis-specified and the optimal policy will be wrong. Second, and just as important, an MDP assumes the transition probabilities P(s' \mid s, a) and rewards R(s, a) are known in advance. When they are not — when an agent must learn the dynamics by trying actions and observing outcomes — you have crossed from planning into reinforcement learning. RL is, in essence, "solving an MDP whose model you have to discover as you go."