---
title: Markov Decision Processes
module: Uncertainty
moduleNumber: 4
lessonNumber: 8
order: 408
summary: >
  When an agent must act repeatedly in a stochastic world, a fixed plan is useless —
  it needs a policy, an action for every state. The Markov decision process makes this
  precise with a transition model, a reward, and a discount factor; the Bellman
  equation characterizes the optimal state utilities, and value iteration and policy
  iteration solve it. Partial observability lifts the problem to belief states, and
  bandits, Monte-Carlo tree search, and scalable POMDP solvers extend it — this is the
  model-known half of reinforcement learning.
topics: [Uncertainty]
sources:
  - book: AIMA
    ref: "Ch. 17 — Making Complex Decisions; §17.1 Sequential Decision Problems; §17.2 Value Iteration"
  - book: AIMA
    ref: "§17.3 Policy Iteration; §17.4 Partially Observable MDPs"
---

This builds on [Making Decisions: Utility Theory](/artificial-intelligence/uncertainty/making-decisions),
which set up expected utility, the MEU principle, and the value of information for a
_single_ decision. Real agents rarely decide once. They act, watch the stochastic
result, and decide again — and because an intended move can slip off course, the agent
needs not a plan but a policy: an action for every state it might land in.

## Sequential decisions: the Markov decision process

An agent in the world acts, observes the result, and acts again. Because chance
can knock it off course, it cannot commit to a fixed sequence of moves; it needs a
rule that says what to do in _every_ situation it might end up in. The framework
for this is the Markov decision process. The canonical
example is a $4 \times 3$ **gridworld**.[^aima-grid] The agent starts at $(1,1)$
and can try to move `Up`, `Down`, `Left`, `Right`. Two terminal squares give
reward $+1$ (at $(4,3)$) and $-1$ (at $(4,2)$); one square, $(2,2)$, is a wall.
Every other square gives a small reward $-0.04$, a mild incentive to finish
quickly. Motion is stochastic: an action moves the agent in its intended direction
with probability $0.8$, and at a right angle with probability $0.1$ each; bumping a
wall leaves it in place.

$$
% caption: The 4x3 gridworld. The agent starts bottom-left; terminal squares give
% +1 and -1; the shaded square is a wall; every other move costs 0.04. An action
% succeeds with probability 0.8 and slips to a right angle with probability 0.1
% each, so an intended Up can drift sideways.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % 4x3 grid
  \foreach \x in {0,1,2,3,4} \draw[black] (\x,0) -- (\x,3);
  \foreach \y in {0,1,2,3} \draw[black] (0,\y) -- (4,\y);
  % wall
  \fill[black] (1,1) rectangle (2,2);
  \node[font=\scriptsize, black] at (1.5,1.5) {wall};
  % terminals
  \node[draw=acc, text=acc, minimum size=6mm, font=\footnotesize] at (3.5,2.5) {+1};
  \node[draw=red, text=red, minimum size=6mm, font=\footnotesize] at (3.5,1.5) {-1};
  % start
  \node[font=\scriptsize] at (0.5,0.5) {START};
  % column / row indices
  \foreach \x/\lab in {0.5/1,1.5/2,2.5/3,3.5/4} \node[font=\scriptsize, black] at (\x,-0.25) {\lab};
  \foreach \y/\lab in {0.5/1,1.5/2,2.5/3} \node[font=\scriptsize, black] at (-0.3,\y) {\lab};
  % transition model inset, drawn well clear of the grid on the right
  \begin{scope}[xshift=5.9cm, yshift=1.5cm]
    \draw[->, acc, thick] (0,0) -- (0,0.9);
    \node[anchor=east, font=\scriptsize, acc] at (-0.1,0.7) {0.8};
    \draw[->, black] (0.12,0) -- (0.85,0);
    \node[anchor=west, font=\scriptsize] at (0.9,0) {0.1};
    \draw[->, black] (-0.12,0) -- (-0.85,0);
    \node[anchor=east, font=\scriptsize] at (-0.9,0) {0.1};
    \node[font=\scriptsize, black, align=center] at (0,-0.6) {intended Up:\\slips sideways};
  \end{scope}
\end{tikzpicture}
$$

Because outcomes are stochastic, a fixed action _sequence_ is useless — an
intended path can slip off course. The agent needs an action for _every_ state it
might land in. This bundle of formal parts is a **Markov decision process**.

> **Definition (Markov decision process).** An MDP is a tuple $(S, A, P, R,
> \gamma)$: a set of states $S$ (with a start state $s_0$); a set of actions
> $A(s)$ available in each state; a **transition model** $P(s' \mid s, a)$ giving
> the probability of reaching $s'$ from $s$ under $a$; a **reward function**
> $R(s)$; and a **discount factor** $\gamma \in [0,1]$. Transitions are
> **Markovian**: $P(s' \mid s, a)$ depends only on the current state, not the
> history.[^aima-mdpdef]

A solution is not a plan but a **policy** $\pi$, a mapping from every state to an
action, with $\pi(s)$ the recommended action in $s$. An **optimal policy**
$\pi^\ast$ is one whose expected utility is highest. Its shape depends delicately on
$R(s)$: with the mild $-0.04$ penalty, the optimal policy in the $4 \times 3$
world is _conservative_ — from $(3,1)$ it takes the long way around rather than
risk slipping into the $-1$ square. Make the step penalty harsher and the agent
sprints for the exit and accepts the risk; make it positive and the agent avoids
_both_ exits forever.[^aima-optpolicy]

### From rewards to the utility of a state

The utility of a policy is the expected utility of the state _sequences_ it
generates. To score a sequence, additivity plus a mild stationarity assumption
leave essentially one coherent choice: **discounted rewards**,

$$
U_h([\,s_0, s_1, s_2, \dots\,]) \;=\; R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) + \cdots \;=\; \sum_{t=0}^{\infty} \gamma^t R(s_t),
$$

where the discount factor $\gamma \in [0,1)$ trades present against future reward.
Discounting also keeps the sum finite over an
infinite horizon: with rewards bounded by $R_{\max}$, the geometric series gives
$\sum_t \gamma^t R_{\max} = R_{\max}/(1-\gamma)$.[^aima-discount] With $\gamma = 1$
the utility is undiscounted (additive), which is safe only when the agent is
guaranteed to reach a terminal state — a **proper policy**.

Fixing $\gamma < 1$, define $S_t$ as the (random) state at time $t$ under policy
$\pi$. The **expected utility of executing $\pi$ starting from $s$** is

$$
U^\pi(s) \;=\; \mathbb{E}\!\left[\, \sum_{t=0}^{\infty} \gamma^t R(S_t) \;\middle|\; \pi,\, S_0 = s \,\right],
$$

and $\pi^\ast_s = \argmax_\pi U^\pi(s)$ is the best policy from $s$.
One consequence of infinite-horizon discounting: the optimal policy is
_independent of the starting state_ — if two runs ever meet at a state $c$, they
have no reason to disagree about what to do from $c$ onward. So we drop the
subscript and write one $\pi^\ast$.[^aima-independent] The **true utility of a
state** is then the expected utility under the optimal policy,
$U(s) = U^{\pi^\ast}(s)$: the long-run reward of being in $s$ and behaving optimally
thereafter. This $U(s)$ is what lets an agent choose actions by one-step MEU,

$$
\pi^\ast(s) \;=\; \argmax_{a \in A(s)} \sum_{s'} P(s' \mid s, a)\, U(s').
$$

Note the two different quantities: $R(s)$ is the immediate, short-term reward for
being in $s$; $U(s)$ is the long-term total reward from $s$ onward. In the
$4 \times 3$ world the utilities are highest near the $+1$ exit and fall off with
distance, because fewer steps of $-0.04$ stand between the agent and the exit.

$$
% caption: State utilities U(s) for the 4x3 world with gamma = 1 and R(s) = -0.04.
% Each cell shows the expected total reward of acting optimally from there;
% utilities rise toward the +1 exit and are eroded by the per-step cost farther
% away.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \foreach \x in {0,1,2,3,4} \draw[black] (\x,0) -- (\x,3);
  \foreach \y in {0,1,2,3} \draw[black] (0,\y) -- (4,\y);
  \fill[black] (1,1) rectangle (2,2);
  % utilities (AIMA Fig 17.3)
  \node[font=\footnotesize] at (0.5,2.5) {0.812};
  \node[font=\footnotesize] at (1.5,2.5) {0.868};
  \node[font=\footnotesize] at (2.5,2.5) {0.918};
  \node[draw=acc, text=acc, minimum size=6mm, font=\footnotesize] at (3.5,2.5) {+1};
  \node[font=\footnotesize] at (0.5,1.5) {0.762};
  \node[font=\footnotesize] at (2.5,1.5) {0.660};
  \node[draw=red, text=red, minimum size=6mm, font=\footnotesize] at (3.5,1.5) {-1};
  \node[font=\footnotesize] at (0.5,0.5) {0.705};
  \node[font=\footnotesize] at (1.5,0.5) {0.655};
  \node[font=\footnotesize] at (2.5,0.5) {0.611};
  \node[font=\footnotesize] at (3.5,0.5) {0.388};
\end{tikzpicture}
$$

### The Bellman equation

The utilities are not independent numbers. Each ties to its neighbors through one
recursive constraint: the utility of a state is its immediate reward plus the
discounted expected utility of the next state, assuming the agent acts optimally.

> **Theorem (Bellman equation).** The true utilities are the unique solution of
> $$U(s) \;=\; R(s) + \gamma \max_{a \in A(s)} \sum_{s'} P(s' \mid s, a)\, U(s').$$
> There is one such equation per state; the max over actions is what makes the
> system nonlinear.[^aima-bellman]

For $(1,1)$ in the gridworld the equation expands over the four actions, each a
weighted sum over the three squares its intended-and-slipped motions can reach;
plugging in the utilities above shows `Up` is the best action. The Bellman
equation is the fixed-point characterization of $U$, and both algorithms below are
just different ways to solve it.

## Value iteration

The $n$ Bellman equations in $n$ unknowns are nonlinear (the `max` is not linear),
so we cannot use linear algebra. Instead, iterate: start with arbitrary utilities,
compute the right-hand side, feed it back into the left, and repeat. Each such
**Bellman update**

$$
U_{i+1}(s) \;\gets\; R(s) + \gamma \max_{a \in A(s)} \sum_{s'} P(s' \mid s, a)\, U_i(s')
$$

is applied to every state simultaneously. This is **value iteration**.[^aima-vi]

```algorithm
caption: $\textsc{Value-Iteration}(mdp, \varepsilon)$ — utilities of states by iterated Bellman update
input: an MDP with states $S$, actions $A(s)$, transitions $P(s' \mid s, a)$, rewards $R(s)$, discount $\gamma$
input: $\varepsilon$, the maximum error allowed in the utility of any state
$U'(s) \gets 0$ for all $s \in S$
repeat
  $U \gets U'$
  $\delta \gets 0$
  for each state $s \in S$ do
    $U'(s) \gets R(s) + \gamma \max_{a \in A(s)} \sum_{s'} P(s' \mid s, a)\, U(s')$
    if $\lvert U'(s) - U(s) \rvert > \delta$ then
      $\delta \gets \lvert U'(s) - U(s) \rvert$
until $\delta < \varepsilon (1 - \gamma) / \gamma$
return $U$
```

**Convergence.** View the update as an operator $B$ on the whole utility vector,
$U_{i+1} \gets B U_i$, and measure distance with the **max norm**
$\lVert U \rVert = \max_s \lvert U(s) \rvert$. The key fact is that $B$ is a
**contraction** by factor $\gamma$:

$$
\lVert B U_i - B U'_i \rVert \;\le\; \gamma\, \lVert U_i - U'_i \rVert.
$$

A contraction has a unique fixed point and drives any two inputs closer on every
application, so value iteration converges to the one solution of the Bellman
equations whenever $\gamma < 1$.[^aima-contraction] Because the true utilities $U$
are that fixed point, $\lVert BU_i - U \rVert \le \gamma \lVert U_i - U \rVert$:
the error shrinks by at least $\gamma$ each sweep, so convergence is exponential.
The termination test $\delta < \varepsilon(1-\gamma)/\gamma$ guarantees the
returned utilities are within $\varepsilon$ of the true ones. In practice the
_policy_ extracted by one-step lookahead becomes optimal well before the utilities
themselves converge — the exact magnitudes stop mattering once one action clearly
dominates.

$$
% caption: Utilities converging under value iteration in the 4x3 world. Every
% state starts at zero; the update propagates reward outward from the +1 exit, and
% each state's estimate climbs to its true utility, states nearer the goal settling
% first.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (6.6,0) node[right, font=\footnotesize] {iterations};
  \draw[->, black] (0,-0.6) -- (0,3.6) node[above, font=\footnotesize] {U estimate};
  \node[anchor=east, font=\scriptsize] at (-0.05,3.0) {1};
  \node[anchor=east, font=\scriptsize] at (-0.05,0) {0};
  \draw[black, dotted] (0,3.0) -- (6.3,3.0);
  % (4,3)-adjacent state: rises fast to ~0.92
  \draw[acc, very thick] (0,0) .. controls (0.7,2.6) and (1.6,2.85) .. (6.2,2.9);
  \node[anchor=west, font=\scriptsize, acc] at (6.25,2.9) {near +1};
  % mid state: rises to ~0.66
  \draw[black, thick] (0,0) .. controls (1.2,1.4) and (2.4,2.0) .. (6.2,2.05);
  \node[anchor=west, font=\scriptsize] at (6.25,2.05) {mid};
  % far state (start): dips slightly then climbs to ~0.7
  \draw[red, thick] (0,0) .. controls (0.6,-0.4) and (1.3,0.4) .. (6.2,2.2);
  \node[anchor=west, font=\scriptsize, red] at (6.25,2.25) {far};
\end{tikzpicture}
$$

## Policy iteration

Value iteration converges on the utilities, then reads off a policy — but often
the policy stops changing long before the utilities settle, since only the
_ordering_ of actions matters. **Policy iteration** exploits this by working on the
policy directly, alternating two steps from an initial policy $\pi_0$:[^aima-pi]

- **Policy evaluation**: given $\pi_i$, compute $U_i = U^{\pi_i}$, the utility of
  each state _if $\pi_i$ were executed_.
- **Policy improvement**: compute a new MEU policy $\pi_{i+1}$ by one-step
  lookahead on $U_i$.

The evaluation step is the reason this is cheap. With the policy fixed, the action
in each state is determined, so the `max` vanishes and the Bellman equation
becomes _linear_:

$$
U_i(s) \;=\; R(s) + \gamma \sum_{s'} P\big(s' \mid s, \pi_i(s)\big)\, U_i(s').
$$

For $n$ states these are $n$ linear equations in $n$ unknowns, solvable exactly in
$O(n^3)$ by standard linear algebra — or approximately, by a few simplified Bellman
sweeps with the policy held fixed (**modified policy iteration**). The loop
terminates when improvement changes nothing; the utilities are then a fixed point
of the Bellman update, so the policy is optimal. Since there are finitely many
policies and each round strictly improves, termination is guaranteed.

```algorithm
caption: $\textsc{Policy-Iteration}(mdp)$ — optimal policy by evaluate-then-improve
input: an MDP with states $S$, actions $A(s)$, transitions $P(s' \mid s, a)$
$U(s) \gets 0$ for all $s \in S$
$\pi \gets$ a random policy
repeat
  $U \gets \textsc{Policy-Evaluation}(\pi, U, mdp)$
  $unchanged \gets \textbf{true}$
  for each state $s \in S$ do
    $a^\ast \gets \argmax_{a \in A(s)} \sum_{s'} P(s' \mid s, a)\, U(s')$
    if $\sum_{s'} P(s' \mid s, a^\ast)\, U(s') > \sum_{s'} P(s' \mid s, \pi(s))\, U(s')$ then
      $\pi(s) \gets a^\ast$
      $unchanged \gets \textbf{false}$
until $unchanged$
return $\pi$
```

Value iteration and policy iteration are the same idea at different granularities:
both alternate _estimating utilities_ and _improving the policy_. Loosening the
schedule — updating any subset of states, with either kind of update — gives
**asynchronous** dynamic programming, which converges under mild conditions and
lets an agent concentrate work on the states a good policy actually visits.

## Partial observability: the belief-state MDP

MDPs assume the environment is **fully observable** — the agent always knows which
state it is in. Drop that and you get a **partially observable MDP** (POMDP), with
all the MDP elements plus a **sensor model** $P(e \mid s)$ giving the probability of
observing evidence $e$ in state $s$. Now the agent cannot execute $\pi(s)$, because
it does not know $s$.[^aima-pomdp]

The fix is to act on what the agent _does_ know: its **belief state** $b$, a
probability distribution over the actual states. After doing action $a$ and
observing $e$, the belief updates by
[filtering](/artificial-intelligence/uncertainty/reasoning-over-time),
$b' = \textsc{Forward}(b, a, e)$. The fundamental result is that the optimal action
depends _only_ on the current belief state — so an optimal policy is a map
$\pi^\ast(b)$ from beliefs to actions. This converts the POMDP into an ordinary
**MDP over the (continuous) belief-state space**, with its own transition model
$P(b' \mid b, a)$ and reward $\rho(b) = \sum_s b(s) R(s)$; solving that belief-MDP
solves the original POMDP.[^aima-belief] The difficulty is that the belief space is
continuous and high-dimensional, so exact POMDP solving is very hard (PSPACE-hard);
practical agents use approximate look-ahead search over dynamic decision networks.

## Bandits, regret, and scalable MDP solvers

The classical picture in this lesson — a fixed, fully known model, solved offline to
optimality by dynamic programming — is only the base of a large modern literature.
Three strands extend it in directions the textbook treatment gestures at but does not
develop.

**The multi-armed bandit** is the MDP stripped to a single state: $k$ actions
("arms"), each returning a reward from an unknown distribution, and the agent wants
to maximize total reward over $T$ pulls. There is no transition dynamics, only the
tension between _exploiting_ the arm that has looked best so far and _exploring_
arms whose value is still uncertain — the exploration/exploitation trade-off in its
purest form. The right yardstick is **regret**, the shortfall against always pulling
the best arm. Lai and Robbins (1985) proved that no strategy can do better than
regret growing as $O(\log T)$, and that this bound is achievable.[^bandit-lai] The
**upper confidence bound** rule UCB1 attains it by adding an exploration bonus to
each arm's empirical mean, picking $\argmax_i\,\hat\mu_i +
\sqrt{2\ln t / n_i}$ so that seldom-tried arms stay attractive until their
estimates sharpen (Auer, Cesa-Bianchi, and Fischer, 2002).[^bandit-ucb] The Bayesian
alternative, **Thompson sampling**, keeps a posterior over each arm's value and pulls
in proportion to the posterior probability that the arm is best; it is decades old
(Thompson, 1933) but its strong empirical and theoretical performance was only
established recently.[^bandit-thompson] Bandits are the theory behind A/B testing,
ad selection, and clinical-trial design, and are the natural setting in which VPI
becomes a live, repeated decision rather than a one-shot calculation.

**When the state space is astronomically large**, value and policy iteration over an
explicit table are hopeless, and the standard tool is _sampling_. **Monte-Carlo tree
search** (MCTS) with the UCT rule — UCB applied to the tree of a sequential decision
problem — estimates action values by rolling out random continuations and
concentrating simulations on promising branches (Kocsis and Szepesvári,
2006).[^mcts] Combined with deep neural networks that supply value and policy priors,
MCTS drives AlphaGo (Silver et al., 2016) and its successors, which solve
enormous game-tree MDPs that no exact method could touch.[^alphago] The same
model-based planning appears in **AlphaZero** and **MuZero**, where the transition
model itself is learned, closing the loop back to reinforcement learning.

**POMDP solving at scale** has its own approximate methods. Exact belief-space value
iteration is intractable, but **point-based value iteration** (Pineau, Gordon, and
Thrun, 2003) keeps the piecewise-linear value function only at a sampled set of
reachable belief points, and the online solver **POMCP** (Silver and Veness, 2010)
runs Monte-Carlo tree search directly in belief space using particle filters. These
turn the belief-MDP idea of this lesson from a theoretical reduction into agents that
run on real robots.

The common thread is that every extension here keeps the MEU objective and the
Bellman structure intact, and only changes _how_ the intractable expectation or
maximization is approximated — by confidence bounds, by sampling, or by learned
function approximators.

## The bridge to reinforcement learning

Everything above assumes the agent is _handed_ the MDP — it knows $P(s' \mid s, a)$
and $R(s)$ and merely computes an optimal policy. That is **planning**, not
learning. The whole apparatus carries over verbatim to
[reinforcement learning](/reinforcement-learning/foundations/markov-decision-processes),
with one thing removed: the model.

> **Definition (Reinforcement learning).** An MDP in which the agent does _not_
> know the transition model $P(s' \mid s, a)$ or the reward function $R(s)$ in
> advance, and must estimate optimal behavior from experienced transitions and
> rewards alone.

The objects are identical — states, actions, a transition model, a reward, a
discount, policies, the utility of a state, the Bellman equation. Value iteration
and policy iteration reappear under the name
[dynamic programming](/reinforcement-learning/tabular-methods/dynamic-programming),
the model-based backbone of RL. What changes is only that the expectations
$\sum_{s'} P(s' \mid s, a)\,U(s')$ can no longer be computed in closed form: without
$P$, the agent must _sample_ the transition by acting, and average the results over
time. Monte-Carlo and temporal-difference methods are those same Bellman updates
with the unknown expectation replaced by a sampled estimate. The MDP theory of
this lesson is RL with a known model; every RL algorithm is a way of running these
same updates while estimating $P$ and $R$ from experience.

[^aima-grid]: **AIMA**, §17.1 — Sequential Decision Problems: the $4 \times 3$ gridworld, the stochastic transition model (0.8 intended, 0.1 to each side), the $-0.04$ per-step reward, and the $\pm 1$ terminal states.
[^aima-mdpdef]: **AIMA**, §17.1 — a Markov decision process is a set of states with an initial state, a set of $\textsc{Actions}(s)$, a Markovian transition model $P(s' \mid s, a)$, and a reward function $R(s)$.
[^aima-optpolicy]: **AIMA**, §17.1 — policies and optimal policies: a policy $\pi$ maps every state to an action; the optimal policy $\pi^\ast$ maximizes expected utility, and its risk profile depends on the sign and magnitude of $R(s)$ for nonterminal states.
[^aima-discount]: **AIMA**, §17.1.1 — Utilities over time: stationarity forces either additive or discounted rewards; the discounted sum $\sum_t \gamma^t R(s_t)$ is finite for $\gamma < 1$, bounded by $R_{\max}/(1-\gamma)$; proper policies permit $\gamma = 1$.
[^aima-independent]: **AIMA**, §17.1.2 — Optimal policies and the utilities of states: $U^\pi(s) = \mathbb{E}[\sum_t \gamma^t R(S_t) \mid \pi]$; with infinite-horizon discounting the optimal policy is independent of the start state, and $U(s) = U^{\pi^\ast}(s)$ enables action selection by one-step MEU.
[^aima-bellman]: **AIMA**, §17.2.1 — The Bellman equation for utilities: $U(s) = R(s) + \gamma \max_a \sum_{s'} P(s' \mid s, a) U(s')$; the true utilities are its unique solution, and the $\max$ makes the system nonlinear.
[^aima-vi]: **AIMA**, §17.2.2 — The value iteration algorithm: the Bellman update applied simultaneously to all states, iterated to a fixed point, with the termination test $\delta < \varepsilon(1-\gamma)/\gamma$.
[^aima-contraction]: **AIMA**, §17.2.3 — Convergence of value iteration: the Bellman operator is a contraction by $\gamma$ in the max norm, so it has a unique fixed point and value iteration converges exponentially fast for $\gamma < 1$.
[^aima-pi]: **AIMA**, §17.3 — Policy Iteration: alternating policy evaluation (linear, $O(n^3)$, or approximate via modified policy iteration) with policy improvement by one-step lookahead; termination when the policy stops changing.
[^aima-pomdp]: **AIMA**, §17.4 — Partially Observable MDPs: a POMDP adds a sensor model $P(e \mid s)$; the agent cannot observe its state, so the optimal action depends on the belief state rather than the physical state.
[^aima-belief]: **AIMA**, §17.4.1–17.4.2 — the belief-state update $b' = \textsc{Forward}(b, a, e)$, the belief-space transition model and reward $\rho(b) = \sum_s b(s) R(s)$, and the reduction of a POMDP to an MDP over the continuous belief space.
[^bandit-lai]: Lai, T. L., and Robbins, H. (1985), "Asymptotically efficient adaptive allocation rules," _Advances in Applied Mathematics_ 6(1): 4–22 — established the $\Omega(\log T)$ lower bound on the regret of any consistent bandit allocation rule and an asymptotically matching strategy.
[^bandit-ucb]: Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002), "Finite-time Analysis of the Multiarmed Bandit Problem," _Machine Learning_ 47: 235–256 — the UCB1 algorithm, which achieves $O(\log T)$ regret uniformly over time by an additive confidence bonus.
[^bandit-thompson]: Thompson, W. R. (1933), _Biometrika_ 25: 285–294 introduced posterior sampling; near-optimal regret guarantees were shown much later, e.g. Agrawal, S., and Goyal, N. (2012), "Analysis of Thompson Sampling for the Multi-armed Bandit Problem," _COLT_.
[^mcts]: Kocsis, L., and Szepesvári, C. (2006), "Bandit based Monte-Carlo Planning," _ECML_ — the UCT algorithm applying UCB to the search tree, the basis of modern Monte-Carlo tree search.
[^alphago]: Silver, D. _et al._ (2016), "Mastering the game of Go with deep neural networks and tree search," _Nature_ 529: 484–489 — combined Monte-Carlo tree search with deep value and policy networks to defeat a professional Go player.