Lecture 20: Value Iteration and Q-learning

Can a learner estimate a good policy without storing an estimate of the entire transition model? This lecture compares plug-in value iteration with synchronous Q-learning in a finite-horizon problem. It then examines how a particular learning rate controls the accumulation of sampling error.

Editorial status. This source preserves the original setup, both algorithms, the theorem claim, the weight identities, the proof outline, the appendix lemma, and all four references. Review notes identify assumptions and gaps that remain unresolved. Routine index and function-domain corrections are made explicitly; the original theorem is not presented as independently verified.

1 Recap: plug-in estimates

The preceding lecture introduced estimates of transition and reward functions for offline learning. Its main comparison was between the value of a policy in the true model and in the estimated, or plug-in, model. Small transition and reward errors can yield small value-function errors under suitable bounds. Here the focus shifts to learning action values directly.

2 Introduction

We study a finite-horizon setting with time-dependent transitions and rewards. The data access in the algorithms below permits fresh samples for each state, action, and time step. This is stronger than access to an arbitrary fixed batch of trajectories: it is a generative-model sampling assumption. The source’s use of “offline” should be read in that specified sense. Additional discussion appears in the Princeton lecture notes [1].

3 Setting

Let $\mathcal S$ and $\mathcal A$ be finite state and action spaces, with cardinalities $S$ and $A$, and let $H$ be the horizon. At time $h\in[H]$, transitions follow $$P_h(s'\mid s,a),\qquad \sum_{s'\in\mathcal S}P_h(s'\mid s,a)=1.$$ The augmented state space $$\mathcal S_{\mathrm{aug}}=\{(s,h):s\in\mathcal S,\ h\in[H]\}$$ separates different times into disjoint layers $\mathcal S_h$. A time-dependent process can then be represented by $$P((s',h')\mid(s,h),a)=P_h(s'\mid s,a)\mathbf{1}\{h'=h+1\}.$$ At the final layer, a terminal layer or absorbing terminal state is required; the displayed formula describes transitions between nonterminal layers. We use zero terminal values at $H+1$.

4 Algorithms for time-dependent finite-horizon problems

4.1 Plug-in value iteration

For clarity, assume rewards are known and deterministic, $$r_h(s,a)\in[0,R_{\max}].$$ The original motivation is that estimating an entire transition distribution can be more demanding than estimating a scalar mean reward. Uniform coverage is implemented here by drawing $N$ independent samples from every $P_h(\cdot\mid s,a)$.

For each $(s,h,a)$, let $s'_1,\ldots,s'_N$ be those samples and define $$\widehat P_h(s'\mid s,a)=\frac1N\sum_{i=1}^N\mathbf{1}\{s'=s'_i\}.$$ Starting from $\widehat V_{H+1}=0$, compute backward in time: $$\begin{align} \widehat Q_h(s,a)&=r_h(s,a)+\sum_{s'}\widehat P_h(s'\mid s,a)\widehat V_{h+1}(s'),\\ \widehat V_h(s)&=\max_{a\in\mathcal A}\widehat Q_h(s,a). \end{align}$$ This is finite-horizon dynamic programming in the estimated model [2]. If the transition model is known exactly, the same recursion recovers the optimal action values. Performance guarantees for the estimated-model procedure are discussed in [3].

4.2 Q-learning

Q-learning stores action values instead of a transition table. At each iteration, it samples a successor state for every state-action-time triple and updates its value estimate. This reduces the storage associated with explicitly representing $P_h$; it does not eliminate the need for adequate sampling.

Initialize $Q_h^{(0)}(s,a)=0$ for $h\in[H+1]$ and keep $V_{H+1}^{(t)}=0$ for all $t$. For each iteration $t=1,\ldots,N$ and each $(s,h,a)$:

1. Draw a fresh $s'_t\sim P_h(\cdot\mid s,a)$.

2. Update Equation (1)$$\begin{equation} \label{eq:update} Q_h^{(t)}(s,a)=(1-\alpha_t)Q_h^{(t-1)}(s,a) +\alpha_t\bigl(r_h(s,a)+V_{h+1}^{(t-1)}(s'_t)\bigr). \end{equation}$$

3. Set $V_h^{(t)}(s)=\max_aQ_h^{(t)}(s,a)$.

The source loops through $h=H,H-1,\ldots,1$. Because the right-hand side uses iteration $t-1$, this is a synchronous update even when implemented in that order. The value function has argument $s$, not $(s,a)$; the latter was a notation error in the original pseudocode.

4.3 Expanding the recursion

Define $$\gamma_t^{(i)}=\alpha_i\prod_{j=i+1}^t(1-\alpha_j),\qquad \gamma_t^{(0)}=\prod_{j=1}^t(1-\alpha_j).$$ Unrolling equation (1) gives $$Q_h^{(t)}(s,a)=\gamma_t^{(0)}Q_h^{(0)}(s,a) +\sum_{i=1}^t\gamma_t^{(i)}\bigl(r_h(s,a)+V_{h+1}^{(i-1)}(s'_i)\bigr).$$ In general, $\sum_{i=1}^t\gamma_t^{(i)}=1-\gamma_t^{(0)}$. The source’s identity $\sum_i\gamma_t^{(i)}=1$ holds when $\alpha_1=1$, as it does for both learning-rate choices considered below. With that condition, Equation (2)$$\begin{equation} \label{eq:expanded} Q_h^{(t)}(s,a)=r_h(s,a)+\sum_{i=1}^t\gamma_t^{(i)}V_{h+1}^{(i-1)}(s'_i). \end{equation}$$ For $\alpha_t=1/t$, every weight is $\gamma_t^{(i)}=1/t$. Other schedules change the relative contribution of early and recent iterates. The analysis studies $$\alpha_t=\frac{H+1}{H+t},$$ which equals $1/t$ at $t=1$ and exceeds it for $t>1$ when $H>0$.

4.4 The theorem as stated in the original notes

For the learning rate above, the source claims that, with probability at least $1-\delta$, Equation (3)$$\begin{equation} \label{eq:original-claim} \left\lVert \frac 1t\sum_{i=1}^t Q_h^{(i)}-Q_h^*\right\rVert_\infty \leq\sqrt{\frac{H^5\log(HSA/\delta)}{t}}. \end{equation}$$ Here $Q_h^*$ is the optimal action-value function of the actual system.

Mathematical review note. The statement does not specify whether it holds for a fixed $t$ or simultaneously over all $t\leq N$, suppresses the dependence on $R_{\max}$, and states a unit constant although the proof uses unspecified constants. Its averaging argument also needs to account for the initial iterate and time-uniform concentration. Equation equation (3) is retained as the original lecture claim, not adopted here as a corrected theorem. A rigorous revision requires an explicit probability event and a completed finite-sample argument.

4.5 Weight identities

The following bounds are taken from Lemma 4.1 of [4], as cited in the original lecture:

The first controls the squared weights in a concentration bound. The second limits the total contribution of one historical iterate to later updates. These are different roles; neither is simply an unqualified statement that all individual weights decay rapidly.

4.6 Proof outline and its remaining obligations

Subtracting the Bellman equation for $Q_h^*$ from equation (2), and inserting $V_{h+1}^*(s'_i)$, gives $$\begin{align} Q_h^{(j)}(s,a)-Q_h^*(s,a) ={}&\sum_{i=1}^j\gamma_j^{(i)} \bigl(V_{h+1}^{(i-1)}(s'_i)-V_{h+1}^*(s'_i)\bigr)\nonumber\\ &+\sum_{i=1}^j\gamma_j^{(i)} \bigl(V_{h+1}^*(s'_i)-(P_hV_{h+1}^*)(s,a)\bigr). \end{align}$$ Let $\Delta_{j,h}(s,a)$ denote the second sum. For fixed $(j,h,s,a)$, it is a weighted sum of centered independent random variables under the stated sampling model. Since $0\leq V_{h+1}^*\leq HR_{\max}$, a Hoeffding bound has scale $$HR_{\max}\sqrt{ \log(1/\varepsilon)\sum_{i=1}^j(\gamma_j^{(i)})^2} \lesssim R_{\max}\sqrt{\frac{H^3\log(1/\varepsilon)}{j}}.$$ Universal factors are suppressed in this display. A union bound over the state-action-time triples gives a factor involving $HSA$; controlling every iterate used by the subsequent sum also requires a justified allocation of the failure probability across $j$.

Write $e_{j,h}=\left\lVert Q_h^{(j)}-Q_h^*\right\rVert_\infty$ and let $d_{j,h}$ be a nonnegative uniform bound on $|\Delta_{j,h}(s,a)|$. The appendix lemma yields $$e_{j,h}\leq\sum_{i=1}^j\gamma_j^{(i)}e_{i-1,h+1}+d_{j,h}.$$ Summing over $j$ and interchanging the finite sums gives $$\begin{align} \sum_{j=1}^t e_{j,h} &\leq\sum_{i=1}^t\left(\sum_{j=i}^t\gamma_j^{(i)}\right)e_{i-1,h+1} +\beta_{t,h}\\ &\leq\left(1+\frac1H\right)\sum_{i=0}^{t-1}e_{i,h+1}+\beta_{t,h}, \qquad \beta_{t,h}=\sum_{j=1}^t d_{j,h}. \end{align}$$ This repairs the source’s mixed $i,j,t$ indices without changing the intended summation. The sum of $j^{-1/2}$ terms has order $\sqrt t$, so the intended sampling contribution is of order $R_{\max}\sqrt{H^3t}$, up to logarithms.

The original notes then propagate the recursion through $H$ layers and write $$\sum_{i=1}^t e_{i,h} \lesssim C\left[1+\left(1+\frac1H\right)+\cdots+ \left(1+\frac1H\right)^H\right]\sqrt{H^3t} \lesssim C\sqrt{H^5t}.$$ This is the source’s scaling argument, with rewards implicitly normalized and logarithms omitted. The $i=0$ terms require separate accounting when the sums are compared across layers. Finally, convexity of the norm gives $$\left\lVert \frac 1t\sum_{i=1}^tQ_h^{(i)}-Q_h^*\right\rVert_\infty \leq\frac1t\sum_{i=1}^te_{i,h}.$$ Thus an appropriate bound on the sum of errors would imply a bound for the averaged iterate. The argument explains the intended $H^{5/2}/\sqrt t$ scale; it leaves the exact statement in equation (3) unresolved.

5 The maximum operator is nonexpansive

The original notes impose nonnegative $Q$-values. The proof does not use that restriction; it is valid for arbitrary real values. This observation is an explicit correction of an unnecessary assumption, not a new claim about Q-learning convergence.

References

[1]

C. Jin, B. Wang, Y. Yan, and Z. Li. ELE524: Foundations of Reinforcement Learning, Lecture 6. Princeton University, Spring 2020.

[2]

M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.

[3]

C. Jin, B. Wang, Y. Yan, and Z. Li. ELE524: Foundations of Reinforcement Learning, Lecture 5. Princeton University, Spring 2020.

[4]

C. Jin, Z. Allen-Zhu, S. Bubeck, and M. I. Jordan. Is Q-Learning Provably Efficient? Advances in Neural Information Processing Systems, 31, 2018.