Markov Decision Processes — From Bandits to Reinforcement Learning

Corresponds to Lattimore & Szepesvári, Chapter 38, the book’s final chapter.

Motivation: actions with long-term consequences

IntuitionBandits plus state

A brewery’s ingredient orders today shape what it can brew next month. A student’s study choices pay off now and in future job prospects. Bandits can’t express this. A Markov decision process adds a state that the learner observes: rewards depend on (state, action), and actions influence the next state. A bandit is an MDP with one state; a contextual bandit is an MDP whose next state ignores the action (Exercise 38.25).

Question	Tool
What is optimal behaviour in a known MDP?	gain, Bellman optimality equation
How do we compute it?	linear programming (polynomial time); value or policy iteration (practical)
How do we learn it with unknown dynamics?	UCRL2: optimism over a confidence set of MDPs
How well can one learn?	$\tilde O(DS\sqrt{An})$ upper bound versus $\Omega(\sqrt{DSAn})$ lower bound

Problem set-up

DefinitionMarkov decision process $M = (\mathcal S,\mathcal A,P,r,\mu)$

states $\mathcal S$ and actions $\mathcal A$ , of sizes $S$ and $A$ (finite MDP if both are finite; take $\mathcal S = [S]$ );
transitions $P_a(s,s')$ : the probability of moving $s\to s'$ under action $a$ , with right-stochastic matrices $P_a$ and rows $P_a(s)\in\mathcal P(\mathcal S)$ ;
deterministic rewards $r_a(s)\in[0,1]$ , also viewed as vectors in $[0,1]^S$ ;
initial distribution $\mu$ .

Protocol: $S_1\sim\mu$ . In each round, observe $S_t$ , choose $A_t$ , receive $r_{A_t}(S_t)$ , then $S_{t+1}\sim P_{A_t}(S_t)$ .

flowchart LR
  O["Observe state S_t"] --> C["Choose action A_t"]
  C --> R["Receive r(A_t, S_t)"]
  R --> T["Next state drawn from P(A_t, S_t)"]
  T --> O

NoteActions are per-state labels

The same action set in every state implies no similarity between $P_a(s)$ and $P_a(s')$ . State-dependent action sets change nothing. The colours in the book’s figures (solid = “increment”, dashed = “decrement”) are only for human readability.

DefinitionHistories and policies

The history $H_t = (S_1,A_1,\ldots,A_{t-1},S_t)$ includes the current state; rewards are recomputable. A policy maps histories to (distributions over) actions.

Class	Depends on	Notation
Memoryless (stationary)	current state only, possibly randomised	$\Pi_M$ , $\pi(a\mid s)$
Deterministic memoryless	current state, no randomisation	$\Pi_{DM}$ , $\pi : \mathcal S\to\mathcal A$
Markov	time index and current state	a sequence of memoryless policies

Under a Markov policy the states form a Markov chain, homogeneous if the policy is memoryless. The infinite interaction exists by Ionescu–Tulcea (Exercise 38.1). Markov policies suffice: for any policy there is a Markov policy with the same state–action marginals, hence the same rewards (Exercise 38.2; Strauch 1966).

Traps and the diameter

WarningTraps make learning hopeless

A trap is a set of states with no escape. A learner discovers that an action leads to a trap only by trying it, so competing with an informed agent is impossible: policies with sublinear regret on all strongly connected MDPs suffer linear regret on MDPs with suboptimal traps (Exercise 38.28). Assume no traps.

DefinitionStrong connectivity and diameter (Def. 38.1)

$M$ is strongly connected (communicating) if every state can reach every other under some policy with positive probability. The diameter is

$D(M) = \max_{s\ne s'}\min_{\pi\in\Pi_{DM}}\mathbb E^\pi\big[\min\{t\ge1 : S_t = s\}\mid S_1 = s'\big] - 1$

the worst-case expected travel time between states, using the best policy for each pair.

Fact	Detail
Different policy per pair	the max is outside the min
Deterministic memoryless suffices	travel times satisfy a shortest-path fixed point (Exercise 38.3)
$D < \infty$	iff strongly connected, for finite MDPs (Exercise 38.4)
Lower limit	$D\ge\log_AS - 3$ : at most $A^k$ states are reachable in $k$ steps (Exercise 38.5)
Meaning	small $D$ means mistakes are cheap to recover from

All MDPs below are strongly connected.

Optimal policies and the Bellman optimality equation

DefinitionGain and optimality (average reward)

$\rho_s^\pi = \lim_{n\to\infty}\frac1n\sum_{t=1}^n\mathbb E^\pi[r_{A_t}(S_t)\mid S_1 = s],\qquad\bar\rho_s^\pi = \limsup_{n\to\infty}(\cdots),\qquad\rho^* = \max_s\sup_\pi\bar\rho_s^\pi$

$\pi$ is optimal if $\rho^\pi = \rho^*\mathbf 1$ . Optimal policies exist for strongly connected MDPs, which is far from trivial. Without strong connectivity, the optimal gain is a vector $\rho^*_s$ (Note 7).

DefinitionMemoryless-policy quantities

$P_\pi(s,s') = \sum_a\pi(a\mid s)P_a(s,s')$ and $r_\pi(s) = \sum_a\pi(a\mid s)r_a(s)$ (38.1).

Stationary transition matrix $P_\pi^* = \lim_n\frac1n\sum_{t<n}P_\pi^t$ , which always exists (Exercise 38.7). Then $\rho^\pi = P_\pi^*r_\pi$ (38.2).
Differential value function (Cesàro sum of excess rewards): $v_\pi = \lim_n\frac1n\sum_{k=1}^nv_\pi^{(k)},\quad v_\pi^{(k)} = \sum_{t=1}^kP_\pi^{t-1}(r_\pi - \rho^\pi)\quad\Rightarrow\quad v_\pi = \big((I - P_\pi + P_\pi^*)^{-1} - P_\pi^*\big)r_\pi \tag{38.3}$ $v_\pi(s) - v_\pi(s')$ is the long-run advantage of starting in $s$ rather than $s'$ . $(I - P + P^*)^{-1}$ is the fundamental matrix, and subtracting $P^*$ gives the deviation matrix.
Poisson equation: $P_\pi^*P_\pi = P_\pi^*$ gives $P_\pi^*v_\pi = 0$ , and $\rho^\pi + v_\pi = r_\pi + P_\pi v_\pi \tag{38.4}$

NoteWhy Cesàro sums (Notes 9–10)

A Cesàro sum averages the partial sums, which smooths out periodicity: $1 - 1 + 1 - \cdots$ has Cesàro sum $\frac12$ . It is used so that $v_\pi$ exists even for periodic chains. The Abel sum $\lim_{\gamma\to1}(1-\gamma)\sum\gamma^na_n$ agrees with the Cesàro sum when the latter exists, and is stronger. Approximating average reward by $\gamma$ -discounted problems with $\gamma\to1$ is the vanishing discount method.

DefinitionSpan, greedy policy, Bellman equation, Bellman operator

$\mathrm{span}(v) = \max_sv(s) - \min_sv(s)$ .
Greedy policy: $\pi_v(s) = \arg\max_a\big(r_a(s) + \langle P_a(s),v\rangle\big)$ , with systematic tie-breaking.
Bellman optimality equation: $\rho + v(s) = \max_a\big(r_a(s) + \langle P_a(s),v\rangle\big)\quad\forall s \tag{38.5}$ $S$ nonlinear equations in $(\rho,v)$ . The $v$ -part is an optimal differential value function.
Bellman operator: $(Tv)(s) = \max_a\big(r_a(s) + \langle P_a(s),v\rangle\big)$ , so (38.5) reads $\rho\mathbf 1 + v = Tv$ .

WarningSolutions are not unique even up to translation (Exercise 38.11)

$v + c\mathbf 1$ is always another solution, but there can be more. Two states, “stay” (reward 0) and “go” (reward $-1$ ): the solutions are exactly $\rho = 0$ with $v(1) - 1\le v(2)\le v(1) + 1$ , a whole band. (This breaks a published proof that assumed $v$ is a limit of value iteration; Bartlett–Tewari 2009.)

TheoremTheorem 38.2 — Bellman equation characterises optimality

A solution $(\rho,v)$ of (38.5) exists.
Any solution has $\rho = \rho^*$ , and the greedy policy $\pi_v$ is optimal.
Hence a deterministic memoryless optimal policy exists.

ProofProof of (2): telescope against the greedy policy

Greedy achieves $\rho$ : with $\pi^* = \pi_v$ , the Bellman equation reads $r_{\pi^*} = \rho\mathbf 1 + v - P_{\pi^*}v$ , so $\frac1n\sum_tP_{\pi^*}^{t-1}r_{\pi^*} = \rho\mathbf 1 + \frac1n(v - P_{\pi^*}^nv)\to\rho\mathbf 1$ .

Nothing beats $\rho$ : take any Markov policy $(\pi_t)$ (sufficient by Exercise 38.2) with $P_\pi^{(t)} = P_{\pi_1}\cdots P_{\pi_t}$ . Greediness gives $r_{\pi_t} + P_{\pi_t}v\le r_{\pi^*} + P_{\pi^*}v = \rho\mathbf 1 + v$ , so

$P_\pi^{(t-1)}r_{\pi_t}\le\rho\mathbf 1 + P_\pi^{(t-1)}v - P_\pi^{(t)}v$

which telescopes, so $\bar\rho^\pi\le\rho\mathbf 1$ .

Existence (1): discounted problems have fixed points (contraction). Choose a deterministic policy greedy along a sequence $\gamma_n\to1$ (finitely many candidates), and pass to the limit with $P^*_\gamma = (1-\gamma)(I - \gamma P)^{-1}\to P^*$ (Exercises 38.8–38.10).

∎

LemmaLemma 38.3 — Value spans are bounded by the diameter

Any Bellman solution has $\mathrm{span}(v)\le D(M)$ , and more precisely $\le(\rho^* - \min_{s,a}r_a(s))D(M)$ (Exercise 38.13). Intuition: you can travel from the worst state to the best in about $D$ steps, losing at most about $\rho^*$ per step, so values can’t differ by more.

TheoremDiscounted MDPs (Exercise 38.8)

$(T_\gamma v)(s) = \max_a\big(r_a(s) + \gamma\langle P_a(s),v\rangle\big)$ is a $\gamma$ -contraction in sup norm. By Banach’s theorem it has a unique fixed point $v^*_\gamma$ , the greedy policy $\pi$ satisfies $v = (I - \gamma P_\pi)^{-1}r_\pi$ , and it is $\gamma$ -discount optimal. Compare the discounted Gittins setting, a special discounted MDP.

Finding an optimal policy (planning)

TheoremTheorem 38.4 — LP for the optimal gain

$\min_{\rho,v}\ \rho\quad\text{s.t.}\quad\rho + v(s)\ge r_a(s) + \langle P_a(s),v\rangle\ \ \forall s,a \tag{38.6}$

is feasible, and every solution has $\rho = \rho^*$ . However, its $v$ need not satisfy the Bellman equation, and its greedy policy need not be optimal (Exercise 38.12).

ProofFeasibility from the Bellman solution; optimality by telescoping

$(\rho^*,v^*)$ is feasible, so $\rho\le\rho^*$ . Conversely, with $\pi^*$ optimal and $(\rho,v)$ feasible, $r_{\pi^*}\le\rho\mathbf 1 + v - P_{\pi^*}v$ . Multiplying by $P_{\pi^*}^t$ and averaging telescopes to $\rho^*\le\rho$ .

∎

TheoremTheorem 38.5 — LP for an optimal value function

$\min_v\ \langle v,\mathbf 1\rangle\quad\text{s.t.}\quad\rho^* + v(s)\ge r_a(s) + \langle P_a(s),v\rangle\ \ \forall s,a,\qquad v(\tilde s) = 0 \tag{38.7}$

For some state $\tilde s$ , every solution satisfies the Bellman equation. (Without the anchor $v(\tilde s) = 0$ , $v$ could decrease without bound.)

ProofThe slack vanishes at a recurrent state, then everywhere

Let $\varepsilon = v + \rho^*\mathbf 1 - Tv\ge0$ . With $\pi^*$ optimal, $\rho^*\mathbf 1\le\rho^*\mathbf 1 - P^*_{\pi^*}\varepsilon$ , so $P^*_{\pi^*}\varepsilon = 0$ . Pick $\tilde s$ with $P^*_{\pi^*}(s,\tilde s) > 0$ for some $s$ (a recurrent state), so $\varepsilon(\tilde s) = 0$ . Then $v - \varepsilon$ is also feasible, and minimality gives $\langle\varepsilon,\mathbf 1\rangle\le0$ , so $\varepsilon = 0$ . In practice, try each $\tilde s$ , or find a recurrent state through the LP dual’s complementary slackness (Note 11).

∎

AlgorithmPolynomial time via the ellipsoid method (§38.3.1)

The ellipsoid method minimises $\langle c,x\rangle$ over a convex $K$ in time polynomial in $n$ and $\log(R/(\delta\varepsilon))$ , given (a) a bounding radius $R$ , (b) a separation oracle, and (c) an inner ball of radius $\delta$ .

(a) Bounded: add $\lVert v\rVert_\infty\le D$ (Lemma 38.3) and $0\le\rho\le1$ , giving $R = \sqrt{1 + D^2S}$ . Use doubling if $D$ is unknown.
(c) Inner ball: add slack $\varepsilon$ to every constraint (38.9). The solution moves by at most $\varepsilon$ .
(b) Oracle (Algorithm 27): for each $s$ compute $a_s^* = \arg\max_a(r_a(s) + \langle P_a(s),v\rangle)$ . If all constraints hold, return “feasible”; otherwise return the violated constraint’s normal $(1, e_s - P_{a_s^*}(s))$ . Extra half-space constraints combine easily (Exercise 38.15).
Approximation is fine (Exercise 38.16): if Bellman holds within $\varepsilon$ , then $\rho\ge\rho^* - \varepsilon$ , and an $\varepsilon'$ -greedy policy is $(2\varepsilon + \varepsilon')$ -optimal.

WarningPolynomial is not practical

The ellipsoid method “should be avoided at all costs” in practice. Use instead:

Value iteration: $v_{k+1} = Tv_k - \max_sv_k(s)$ (renormalised because $v_k$ grows like $k$ ; the greedy policy is unchanged).
Policy iteration: alternate evaluating $v_{\pi_k}$ and acting greedily (needs a small modification to converge).
Other LP methods.

These work well but lack polynomial guarantees under weak assumptions (Bertsekas, vol. 2).

Learning in Markov decision processes

Setting. The rewards $r$ are known, the transitions $P$ unknown. Unknown stochastic rewards are an easy extension with optimistic reward estimates (Exercise 38.23).

DefinitionRegret

$\hat R_n = n\rho^* - \sum_{t=1}^nr_{A_t}(S_t)$

This compares against the asymptotic gain, which is fine because the best $n$ -step value satisfies $v^*_n(s)\le n\rho^* + D$ (Exercise 38.17).

TheoremTheorem 38.6 — Upper bound (UCRL2)

An efficiently computable policy achieves, on every MDP with $S$ states, $A$ actions, rewards in $[0,1]$ and any initial distribution, with probability $1-\delta$ ,

$\hat R_n < C\,D(M)\,S\sqrt{An\log(nSA/\delta)}$

and $\mathbb E[\hat R_n]\le1 + CD(M)S\sqrt{2An\log n}$ (38.12).

TheoremTheorem 38.7 — Lower bound

For $S\ge3$ , $A\ge2$ , $D\ge6 + 2\log_AS$ and $n\ge DSA$ , every policy has some MDP with diameter at most $D$ and

$\mathbb E[\hat R_n]\ge C\sqrt{DSAn}$

The gap to the upper bound is at least $\sqrt{DS}$ .

UCRL2: upper confidence bounds for reinforcement learning

DefinitionConfidence sets for transitions

Empirical transitions $\hat P_{t,a}(s,s') = \frac{\sum_{u\le t}\mathbb I\{S_u = s,A_u = a,S_{u+1} = s'\}}{1\vee T_t(s,a)}$ . Each state–action pair gets an $\ell_1$ ball:

$\mathcal C_t(s,a) = \Big\{P\in\mathcal P(\mathcal S) : \lVert P - \hat P_{t-1,a}(s)\rVert_1\le\sqrt{\frac{S L_{t-1}(s,a)}{1\vee T_{t-1}(s,a)}}\Big\} \tag{38.13}$

with $L_t(s,a) = 2\log\frac{4SAT_t(s,a)(1 + T_t(s,a))}\delta$ (and $L = 1$ , i.e. the whole simplex, when unvisited). $L_t\le L = 2\log\frac{4SAn(n+1)}\delta$ . The full set $\mathcal C_t$ is the product over pairs. The radius is the Bretagnolle–Huber–Carol $\ell_1$ bound for categorical distributions.

AlgorithmUCRL2 (Algorithm 28; Auer, Jaksch, Ortner)

Proceed in phases $k = 1, 2, \ldots$ . At phase start $\tau_k$ :

Optimistic planning: find $(\rho_k,v_k,P_k)$ with $P_k\in\mathcal C_{\tau_k}$ solving the Bellman equation in the most optimistic plausible MDP: $\rho_k + v_k(s) = \max_a\big(r_a(s) + \langle P_{k,a}(s),v_k\rangle\big),\qquad\rho_k = \max_s\max_{\pi\in\Pi_{DM}}\max_{P\in\mathcal C_{\tau_k}}\rho_s^\pi(P) \tag{38.16}$
Act: play $\pi_k$ , greedy with respect to $v_k$ .
Doubling: end the phase when the visit count of the current state–action pair reaches twice its value at phase start.

ImportantWhy phases are necessary (Exercise 38.19)

Re-planning every round can make an optimistic learner dither. On a two-state MDP where both states pay $\frac12$ for staying and switching pays 0, infinite-horizon optimism keeps believing the other state is slightly better and alternates, paying linear regret. Long-term plans should be followed for a while. Doubling phases also mean only $O(SA\log n)$ re-plans.

The extended MDP

DefinitionOptimism as planning in a bigger MDP

The extended MDP $\tilde M_k$ has the same states, enlarged actions $\tilde{\mathcal A}_s = \{(a,P) : a\in\mathcal A,\ P\in\mathcal C_{\tau_k}(s,a)\}$ , reward $r_a(s)$ , and transition $P$ . The agent chooses both an action and a plausible transition law. Its optimal policy is exactly the optimistic policy in (38.16). (The idea first appeared in MBIE; Strehl–Littman 2008.)

TheoremProperties of the extended MDP

Strongly connected: every confidence ball contains a transition with $P(s,s') > 0$ for any $s'$ , so (38.16) has constant-gain solutions (Exercise 38.20).
Finite in effect: each $\ell_1$ ball is a convex polytope, and restricting to its finitely many vertices doesn’t change the optimum.
Diameter at most $D(M)$ on the good event: the true $P$ is among the choices, so span $(v_k)\le D$ (Lemma 38.3). It is also at most $\sqrt n$ always, since a $1\wedge1/\sqrt n$ jump probability is always plausible, which bounds the LP’s radius.

AlgorithmThe inner optimisation is a sort (§38.5.2)

The oracle needs, for each $(s,a)$ , $\max_{P\in\mathcal C(s,a)}\langle P,v\rangle$ : maximise a linear function over $\ell_1$ -ball ∩ simplex. Sort states by $v$ , put as much mass as the $\ell_1$ budget allows on the highest-value state, and take the excess mass from the lowest-value states. Total cost $O(S(A + \log S))$ per oracle call. Combined with Algorithm 27 and the ellipsoid method, the optimistic policy is polynomial-time computable. (The original UCRL papers used extended value iteration, which is practical but not polynomial.)

Proof of the upper bound

ProofStep 1: Failure event and optimism

Let $E_k$ be the rounds of phase $k$ ( $K$ phases) and $F$ the event that $P\notin\mathcal C_{\tau_k}$ for some $k$ . By the categorical $\ell_1$ concentration with a union bound over pairs and sample counts (the Markov property makes the samples effectively independent), $\mathbb P(F)\le\delta/2$ (Lemma 38.8, Exercise 38.21). On $F^c$ the truth is plausible, so $\rho^*\le\rho_k$ (optimism) and

$\hat R_n\le\sum_{k=1}^K\tilde R_k,\qquad\tilde R_k = \sum_{t\in E_k}\big(\rho_k - r_{A_t}(S_t)\big)$

∎

ProofStep 2: Regret within a phase via the Bellman equation

On $F^c$ , shift $v_k$ so that $\lVert v_k\rVert_\infty\le\frac12\mathrm{span}(v_k)\le\frac D2$ . For $t\in E_k$ the Bellman equation in $M_k$ gives $\rho_k - r_{A_t}(S_t) = -v_k(S_t) + \langle P_{k,A_t}(S_t),v_k\rangle$ . Split the optimistic transition into the true one plus an error:

$\tilde R_k\le\underbrace{\sum_{t\in E_k}\big(\langle P_{A_t}(S_t),v_k\rangle - v_k(S_t)\big)}_{(A)} + \underbrace{\frac D2\sum_{t\in E_k}\lVert P_{k,A_t}(S_t) - P_{A_t}(S_t)\rVert_1}_{(B)} \tag{38.20}$

(A) telescopes plus a martingale: inserting $v_k(S_{t+1})$ gives $(A)\le D + \sum_{t\in E_k}(\mathbb E_t[v_k(S_{t+1})] - v_k(S_{t+1}))$ , using span $(v_k)\le D$ for the boundary terms.
(B) confidence widths: both $P_k$ and $P$ lie in the $\ell_1$ ball, so $(B)\le\frac{D\sqrt{LS}}2\sum_{s,a}\frac{T^{(k)}(s,a)}{\sqrt{1\vee T_{\tau_k-1}(s,a)}}$ .

∎

ProofStep 3: Sum over phases

Martingale: $\sum_t(\mathbb E_t[v_{K_t}(S_{t+1})] - v_{K_t}(S_{t+1}))\le D\sqrt{n\log(2/\delta)/2}$ with probability $1 - \delta/2$ , by Hoeffding–Azuma with a random range.
Widths: doubling makes $\sum_k\frac{T^{(k)}}{\sqrt{1\vee T_{\tau_k-1}}}\le(\sqrt2 + 1)\sqrt{T_n(s,a)}$ (Exercise 38.22, the discrete version of $\int f'/\sqrt f = 2\sqrt f$ ). Then by Cauchy–Schwarz, $\sum_{s,a}\sqrt{T_n(s,a)}\le\sqrt{SAn}$ .
Number of phases: each pair’s count can double at most $1 + \log_2T_n(s,a)$ times, so $K\le SA(1 + \log_2\frac n{SA})$ , contributing $KD$ .

Total: $\hat R_n\lesssim DSA\log\frac n{SA} + D\sqrt{n\log\frac1\delta} + D\sqrt{LS}\sqrt{SAn} = O(DS\sqrt{An\log(nSA/\delta)})$ .

∎

IntuitionWhere $D$ and $S$ come from

$D$ is the scale of value differences, because a transition error of $\ell_1$ size $\epsilon$ moves the value by up to $\epsilon\cdot\mathrm{span}(v)\approx\epsilon D$ .
One $\sqrt S$ comes from the $\ell_1$ radius of an $S$ -dimensional distribution. The other $\sqrt S$ comes from Cauchy–Schwarz over $SA$ pairs, giving $\sqrt{SA}$ .

Note 16: removing the spurious $\sqrt S$ means bounding $\langle\hat P - P,v_k\rangle$ directly, but $v_k$ depends on $\hat P$ . This dependence is “pernicious” and has spoiled several attempts.

Proof of the lower bound

DefinitionThe hard MDP

A tree of $S-2$ states with branching factor at most $A$ and deterministic transitions, rooted at $s_\circ$ , with leaves $s_1, \ldots, s_L$ .
Two absorbing-ish states $s_g$ (reward 1) and $s_b$ (reward 0). Each stays put with probability $1 - \delta$ and returns to the root with probability $\delta = 4/D$ .
From leaf $s_i$ , action $a$ goes to $s_g$ with probability $\frac12 + \varepsilon(a,i)$ , else to $s_b$ . Here $\varepsilon\equiv0$ except for one leaf–action pair, which has $\varepsilon = \Delta$ .

The diameter is at most $D$ regardless of $\Delta$ (Claim 38.9).

IntuitionAn MDP that is secretly a bandit

Each visit to the root lets the learner pick one of $k = LA = \Omega(SA)$ leaf–action “meta-arms”, each a Bernoulli $(\frac12 + \varepsilon)$ coin for entering the good state. Rewards then accrue for about $D$ rounds. So there are about $n/D$ decisions with stakes of about $D$ each, and the regret is about $D\sqrt{k\cdot n/D} = \sqrt{nDSA}$ .

ProofProof of Theorem 38.7 (Assouad-style, as in Exercise 15.2)

Step 1: Setup. $M_0$ has no special pair, and $M_j$ makes pair $j$ special. Stop at $\tau$ , when the root has been visited about $n/D$ times. Let $T_j$ count plays of pair $j$ before $\tau$ , and $T_\sigma = \sum_jT_j$ . Claims: $DE_0[T_\sigma]/n\in[c_1,c_2]$ (Claim 38.10), and the regret in $M_j$ is $R_{nj}\ge c_3\Delta D\,E_j[T_\sigma - T_j]$ (Claim 38.11; Exercise 38.24).

Step 2: Divergence. $M_0$ and $M_j$ differ only at pair $j$ , so by the stopped chain rule, $D(\mathbb P_0,\mathbb P_j) = E_0[T_j]\,d(\frac12,\frac12 + \Delta)\le4\Delta^2E_0[T_j]$ for $\Delta\le\frac14$ (38.22–38.23; Exercise 38.30).

Step 3: Pinsker and summing over $j$ . Since $0\le T_\sigma - T_j\le n/D$ , $E_j[T_\sigma - T_j]\ge E_0[T_\sigma - T_j] - \frac{n\Delta}D\sqrt{2E_0[T_j]}$ . Summing over $j$ with Cauchy–Schwarz, $\sum_jE_j[T_\sigma - T_j]\ge\frac{c_1n(k-1)}D - \frac{n\Delta}D\sqrt{\frac{2c_2nk}D}\ge\frac{c_1n(k-1)}{2D}$ for $\Delta\approx\frac{c_1(k-1)}2\sqrt{\frac D{2c_2nk}}$ .

Step 4: some $j$ has $E_j[T_\sigma - T_j]\gtrsim n/D$ . Then $R_{nj}\gtrsim D\Delta\cdot\frac nD\approx\sqrt{DSAn}$ .

∎

Notes

WarningLarge MDPs are hard (Notes 1–2)

Real MDPs have millions or billions of states, so $DS\sqrt{An}$ can be vacuous, and the lower bound says that without structural assumptions learning is genuinely hard. Choosing the state is a trade-off. It must be observable and Markov; enlarging it (the full history always works) improves fidelity but slows learning.

DefinitionVariants (Notes 3–8)

Random rewards: a joint kernel over (next state, reward), with mean reward $r_a(s)$ .
Episodic MDPs: an absorbing state is reached almost surely. Average reward is meaningless there, so maximise total (possibly discounted) reward. Finite-horizon: absorption after a fixed number of steps.
POMDPs: only observations of the state are seen. They can be converted to MDPs on histories or belief states (posteriors over the hidden state), but computing optimal policies is hard in general (Papadimitriou–Tsitsiklis 1987). Compare the Bayesian bandit posterior-as-state view.
Terminology: agent / decision maker / controller; environment / plant; stochastic optimal control (control theory, average cost) versus multistage stochastic programming (operations research, episodic).
Finer criteria: bias optimality (gain optimal and $v_{\pi^*}\ge v_\pi$ ), Blackwell optimality, $n$ -discount optimality.

WarningUCRL2 is brittle (Notes 13–14)

Unreachable high-reward state: a single unreachable state whose reward exceeds $\rho^*$ forces linear regret, because the optimistic MDP keeps trying to reach it (Exercise 38.27). SCAL (Fruit et al. 2018) fixes this by working with the reachable sub-MDP.
Traps, redefined (Exercise 38.29): the maximal end components (MECs) form a directed acyclic graph, and its sinks are closed, strongly connected sub-MDPs. Reasonable policies can’t control which sink they fall into, so regret should restart once trapped: $R'_n = \mathbb E[\tau + \sum_{t\ge\tau}r - n\rho^*(M_I)]$ , with the target $O(D(M_I)\lvert C_I\rvert\sqrt{An\log n})$ . This definition still ignores how fast the learner gets trapped.

ExampleContextual bandits as MDPs (Exercise 38.25)

If $P_a(s) = p$ for all $s, a$ , the next state ignores the action: a contextual bandit. The optimal policy is per-state greedy with gain $\sum_sp(s)\max_ar_a(s)$ . The diameter is $D = \max_s1/p(s)$ (geometric hitting times). One UCB per state gives $O(\sqrt{SAn})$ , as in one bandit per context. UCRL2’s $DS\sqrt{An}$ is loose here: its bound pays for planning that this problem doesn’t need. (Worked here.)

ExampleRiverSwim (Exercise 38.26)

States $1, \ldots, S$ . “Left” drifts back deterministically, with reward $0.05$ in state 1. “Right” swims against a current: up with probability 0.3, stay 0.6, down 0.1 (state 1: up 0.3, stay 0.7), with reward 1 in state $S$ (stay 0.9). Always swimming right gives a birth–death chain with up/down ratio 3, so $\pi(s)\propto3^{s-1}$ and

$\rho^* = \frac{2\cdot3^{S-1}}{3^S - 1}\approx\frac23\quad(S = 5:\ \approx0.67)$

far above $0.05$ . ε-greedy with empirical models stays near the bank: the reward is too far away to stumble upon. UCRL2 deliberately explores upstream because it is optimistic about unvisited states. (Gain worked here.)

RemarkHistory and the wider literature

Foundations: Bellman (1954; his autobiography mentions encountering Thompson’s bandit paper); Puterman (OR view); Bertsekas (control view); Ross; Kallenberg’s notes; Arapostathis et al. on average-reward theory. RL: Sutton–Barto; Bertsekas–Tsitsiklis; Szepesvári (2010).
Regret: UCRL/UCRL2 (Auer et al. 2009; Jaksch et al. 2010). PSRL, i.e. Thompson sampling for RL (Strens 2000; Osband et al. 2013). Agrawal–Jia (2017) attempted to improve the $S$ dependence, but the proof has unpatched holes. Episodic: $\tilde O(\sqrt{HSAn})$ via Bernstein/Freedman bonuses and backward induction (Azar et al. 2017), with large lower-order terms. Logarithmic instance-dependent bounds: Tewari–Bartlett (flawed constants), Auer–Ortner; asymptotically optimal constants with known supports (Burnetas–Katehakis 1997).
Structured MDPs: LQR with $O(\sqrt n)$ regret (Abbasi-Yadkori–Szepesvári 2011); Lipschitz MDPs with $O(n^{(2d+1)/(2d+2)})$ (Ortner–Ryabko). Optimistic algorithms are often computationally intractable here, which Thompson sampling may fix.
PAC-MDP (discounted): R-max, MBIE, delayed Q-learning, MorMax, UCRLγ.
Adversarial rewards with stochastic transitions: Even-Dar et al. (2004); Neu et al. (2014). Fully adversarial: Abbasi-Yadkori et al. (2013).

Quick reference

Object	Statement	Note
MDP	$(\mathcal S,\mathcal A,P,r,\mu)$	bandit = one state
Diameter	$\max_{s\ne s'}\min_\pi\mathbb E[\text{hit time}] - 1$	finite iff strongly connected; $\ge\log_AS - 3$
Gain	$\rho^\pi = P^*_\pi r_\pi$	average reward
Value	$v_\pi = ((I - P_\pi + P_\pi^)^{-1} - P_\pi^)r_\pi$	Cesàro sum
Poisson	$\rho^\pi + v_\pi = r_\pi + P_\pi v_\pi$
Bellman	$\rho + v = Tv$ , $(Tv)(s) = \max_a r_a(s) + \langle P_a(s),v\rangle$	non-unique solutions
Optimality	greedy w.r.t. any solution is optimal; deterministic memoryless suffices
Span	$\mathrm{span}(v)\le D$
Discounted	$T_\gamma$ is a $\gamma$ -contraction	vanishing discount gives average reward
LP	$\min\rho$ s.t. $\rho + v\ge r_a + P_av$ ; then $\min\langle v,\mathbf 1\rangle$ with $v(\tilde s) = 0$	ellipsoid + oracle
Practice	value / policy iteration	no polynomial guarantee
Regret	$n\rho^* - \sum r_{A_t}(S_t)$	$v_n^\le n\rho^ + D$
Confidence set	$\ell_1$ ball, radius $\sqrt{SL/T}$	categorical concentration
Extended MDP	choose (action, plausible $P$ )	strongly connected; sort-based inner max
UCRL2	optimistic plan, doubling phases	$O(DS\sqrt{An\log(nSA/\delta)})$
Lower bound	tree → good/bad states ≈ bandit with $SA$ arms	$\Omega(\sqrt{DSAn})$
Gap	$\sqrt{DS}$	$v_k$ dependent on $\hat P$

Facts to keep to hand

MDPs are bandits with consequences. The state carries the effect of past actions. Without traps (strong connectivity, finite diameter), average-reward optimality is constant across states and is achieved by a deterministic memoryless policy greedy with respect to any solution of the Bellman optimality equation.
Planning is linear programming. The optimal gain and value function solve two LPs, polynomial-time via the ellipsoid method with a greedy separation oracle and the span ≤ diameter bound. In practice, value and policy iteration are used.
Learning is optimism over MDPs. UCRL2 builds $\ell_1$ confidence balls on transitions, plans in the extended MDP where the agent also picks the most favourable plausible dynamics, and commits to that plan until some visit count doubles. Its regret is about $DS\sqrt{An}$ : diameter from value spans, $S$ from $\ell_1$ widths and Cauchy–Schwarz.
The lower bound is a disguised bandit. About $SA$ meta-arms, each decision worth about $D$ rounds, give $\sqrt{DSAn}$ . Closing the $\sqrt{DS}$ gap is open and delicate, because the optimistic value function depends on the empirical model it would be paired with.

References

Lattimore & Szepesvári, Bandit Algorithms — Chapter 38
Jaksch, Ortner & Auer, “Near-optimal regret bounds for reinforcement learning” (2010)
Puterman, Markov Decision Processes (2009); Bertsekas, Dynamic Programming and Optimal Control (2012)
Sutton & Barto, Reinforcement Learning: An Introduction (2018)

Related