Notation
\[ \newcommand{\E}{\mathbb{E}} \newcommand{\R}{\mathbb{R}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\BR}{\operatorname{BR}} \newcommand{\eps}{\varepsilon} \newcommand{\given}{\,\vert\,} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\sm}{\setminus} \newcommand{\defeq}{\equiv} \]
The book deliberately changes dialect once, at the start of Chapter 2, because the lectures do. Chapter 1 is dynamic programming and speaks the economist’s notation; everything after it is reinforcement learning and speaks the RL literature’s. The switch is announced where it happens, but the two conventions are collected here side by side so nothing has to be reconstructed from memory.
The one deliberate switch
| Chapter 1 (dynamic programming) | Chapters 2 to 4 (reinforcement learning) | |
|---|---|---|
| Discount factor | \(\beta\) | \(\gamma\) |
| Policy | deterministic, \(a=\pi(s)\) | stochastic, \(a_{t}\sim\pi(\cdot\given s_{t})\), so \(\pi(a\given s)\) is a probability |
| Reward at \(t\) | \(r(s_{t},a_{t})\) | \(r_{t+1}\), the reward for acting at \(t\) |
The reward indexing in the third row is worth care. From Chapter 2 onward, \(r_{t+1}\) is the reward received for taking \(a_{t}\) in \(s_{t}\). The offset looks gratuitous until an update has to be written down: it makes \((s_{t},a_{t},r_{t+1},s_{t+1})\) the natural unit of experience, which is exactly what Equation 3.3, Equation 3.7 and Equation 3.9 consume.
The problem
| Symbol | Meaning |
|---|---|
| \(s\in\mathcal{S}\) | state; \(\mathcal{S}\) finite throughout |
| \(a\in\mathcal{A}\), \(\mathcal{A}(s)\) | action; the actions available at \(s\) |
| \(p(s'\given s,a)\) | transition probability |
| \(r(s,a)\), \(r_{t+1}\) | expected reward for the pair; the realized reward at \(t+1\) |
| \(\gamma\in(0,1)\) | discount factor. Load-bearing: it is the contraction modulus in Theorem 3.1 and what makes \(I-\gamma\mathbf{P}_{\pi}\) invertible in Theorem 4.2 |
| \(\pi\), \(\pi^{*}\) | policy; an optimal policy |
| \(\mu(s)\) | the distribution over starting states, used to scalarize the objective in Equation 4.3 |
Values
| Symbol | Meaning |
|---|---|
| \(v_{\pi}(s)\) | state value: expected discounted return from \(s\) under \(\pi\) |
| \(v^{*}(s)\) | optimal state value |
| \(q_{\pi}(s,a)\) | action value: take \(a\) in \(s\), follow \(\pi\) thereafter (Definition 1.3) |
| \(q^{*}(s,a)\) | optimal action value. Q-learning estimates this directly (Equation 3.10); Sarsa estimates \(q_{\pi}\) (Equation 3.8) |
| \(r_{\pi}(s)\), \(p_{\pi}(s'\given s)\) | reward and transition averaged against \(\pi\) (Definition 2.1) |
| \(\mathbf{v},\mathbf{r}_{\pi},\mathbf{P}_{\pi}\) | the vector and matrix forms of the above (Equation 1.5) |
Three things vary independently and are easy to conflate.
- What is being valued: a state (\(v\)) or a state-action pair (\(q\)).
- Under which policy: a given \(\pi\) (subscript \(\pi\), an evaluation object) or the best one (superscript \(*\), an optimality object).
- Estimate or truth: no decoration is the true value; a time subscript \(v_{t},q_{t}\) is the running estimate; a hat \(\hat{v},\hat{q}\) is a parameterized approximation.
So \(q_{t}(s,a)\) is the time-\(t\) estimate of the action value, \(q_{\pi}\) is what Sarsa converges to, \(q^{*}\) is what Q-learning converges to, and \(\hat{q}(s,a,w)\) is a function of parameters standing in for a table.
Estimates, steps, and errors
| Symbol | Meaning |
|---|---|
| \(v_{t}(s)\), \(q_{t}(s,a)\) | time-\(t\) estimates |
| \(\alpha_{t}\), \(\alpha_{t}(s)\), \(\alpha_{t}(s,a)\) | step size, in general depending on which state or pair was visited. \(\alpha_{t}(s)=0\) when \(s\neq s_{t}\), which is why \(\sum_{t}\alpha_{t}(s)=\infty\) is an exploration condition in disguise |
| \(\eps\) | exploration probability of an \(\eps\)-greedy policy (Definition 2.2) |
| \(\bar{v}_{t}\) | TD target, \(r_{t+1}+\gamma v_{t}(s_{t+1})\) (Definition 3.2) |
| \(\delta_{t}\) | TD error, \(\bar{v}_{t}-v_{t}(s_{t})\) |
| \(G_{t}\) | realized discounted return from \(t\), the Monte Carlo estimate of \(q_{\pi}\) |
| \(\Delta_{k}\), \(\eta_{k}\) | estimation error and noise, in the convergence proofs |
| \(\mathcal{H}_{k}\) | the history \(\{\Delta_{k},\Delta_{k-1},\dots\}\). Every conditional expectation in the proofs is taken against it |
| \(\|x\|_{\infty}\) | maximum over the index set, \(\max_{s}|x(s)|\) or \(\max_{(s,a)}|x(s,a)|\) |
Parameters
Two different things get parameterized, in two different chapters, and they are not the same object.
| Symbol | Parameterizes | Where |
|---|---|---|
| \(w\in\R^{m}\) | a value: \(\hat{v}(s,w)\) or \(\hat{q}(s,a,w)\) | Chapter 3, Equation 3.11 |
| \(\phi(s)\) | the feature vector of \(s\), so that \(\hat{v}(s,w)=\phi^{\!\top}(s)w\) in the linear case | Chapter 3, Example 3.1 |
| \(\theta\in\R^{m}\) | the policy itself: \(\pi(a\given s,\theta)\) | Chapter 4 |
| \(J(\theta)\) | the scalar objective \(\sum_{s}v_{\pi}(s)\mu(s)\) | Chapter 4, Equation 4.3 |
| \(d_{\pi,\mu}(s)\) | discounted state visitation distribution | Chapter 4 |
| \(\nabla_{\theta}\ln\pi(a\given s,\theta)\) | the score. The log trick is what turns the policy gradient into an expectation the agent can sample | Chapter 4 |
\(w\) and \(\theta\) are the difference between the last two chapters. Chapter 3 parameterizes a value and reads a policy off it by \(\argmax\); Chapter 4 parameterizes the policy and never forms a table of values at all. Actor-critic uses both at once: \(\theta\) for the actor, \(w\) for the critic.
Macros used in the source
For anyone reading the .qmd source rather than the rendered page: \(\E\) is \E, the conditional bar \(\given\) is \given, \(\argmax\) is \argmax, \(\defeq\) is \defeq, \(\eps\) is \eps, and \(\R\) is \R. They are defined in _macros.qmd, which every chapter includes.