Revision
Hyperparameters & step sizes
What each hyperparameter in Chapters 2–9 controls, what happens when it is too small or too large, and the book's guidance — with a special focus on constant vs varying step sizes.
1. The step size α — constant vs varying
Nearly every method uses the rule $\textit{New}\leftarrow\textit{Old}+\alpha[\textit{Target}-\textit{Old}]$ (2.4). The step size decides how much each new target moves the estimate, and therefore how the estimate weights old vs new data.
| Schedule | Formula | Satisfies (2.7)? | Behaviour | Where in the book |
|---|---|---|---|---|
| Sample average | $\alpha_n=1/n$ | yes | Equal weight to all targets; converges to the mean; initial bias vanishes after one update; adapts ever more slowly | Ch 2 (2.3), Ch 5 MC averages |
| Constant | $\alpha_n=\alpha$ | no ($\sum\alpha^2=\infty$) | Exponential recency weighting $\alpha(1-\alpha)^{n-i}$; never fully converges; tracks nonstationary targets; permanent (decaying) initial bias | Ch 2 (2.5), constant-α MC (6.1), TD, Sarsa, Q-learning, Ch 9 |
| Polynomial decay | $\alpha_n=1/n^p,\ \tfrac12\lt p\le1$ | yes | Between the two; still converges | Stochastic approximation theory |
| Too-fast decay | $\alpha_n=1/n^2$ | no ($\sum\alpha_n\lt\infty$) | Steps die out before overcoming the initial value — may stall short of the target | Pitfall |
| Unbiased constant trick | $\beta_n=\alpha/\bar o_n,\ \bar o_n=\bar o_{n-1}+\alpha(1-\bar o_{n-1})$ | no (→ α) | $\beta_1=1$ removes initial bias; then behaves like constant α | Ex 2.7 |
| Weighted IS step | $W_n/C_n$ | data-dependent | Weighted average of returns; bounded variance | Ch 5 (5.8) |
| Tile-coding step | $\alpha=1/(\tau n)$ for $n$ tilings | constant | $\tau=1$ ⇒ one-trial learning; $\tau=10$ ⇒ ~10 presentations | Ch 9 §9.5.4 |
| General linear rule | $\alpha=(\tau\E[\mathbf x^\top\mathbf x])^{-1}$ | constant | Learn in ≈ τ experiences with similar features | Ch 9 (9.19) |
| Fourier per-feature | $\alpha_i=\alpha/\|\mathbf c^i\|$ | constant | Smaller steps for high-frequency features | Ch 9 §9.5.2 |
| No step size | LSTD: $\mathbf w=\hat{\mathbf A}^{-1}\hat{\mathbf b}$ | — | Needs ε; never forgets (bad when π changes) | Ch 9 §9.8 |
$$\begin{aligned}\sum_{n=1}^\infty\alpha_n&=\infty&&\text{steps large enough to overcome initial conditions and noise}\\ \sum_{n=1}^\infty\alpha_n^2&\lt\infty&&\text{steps eventually small enough to converge}\end{aligned}$$
Robbins–Monro conditions — convergence with probability 1(2.7)
The core trade-off in one sentence
Decreasing step sizes (meeting 2.7) converge on stationary problems; constant step sizes keep tracking on nonstationary ones — and since RL targets are effectively nonstationary (the policy changes in GPI; bootstrapped targets change even for a fixed policy), the book mostly uses constant α. Decreasing sequences "often converge very slowly or need considerable tuning" and "are seldom used in applications".
Try it: step-size schedules on a noisy target
Targets are drawn from $\mathcal N(\mu_t, \sigma^2)$. With "jump", the true mean changes from 1 to 3 halfway (a nonstationary problem). Every estimator starts at $Q_1=0$.
Estimates
Step size used at each step
Step size by chapter — quick reference
| Chapter | Typical choice in the book | Notes |
|---|---|---|
| 2 Bandits | 1/n (stationary) or α = 0.1 | Gradient bandit α ≈ 0.1–0.4; Fig 2.6 sweeps 1/32 … 4 |
| 4 DP | none (expected updates assign the target exactly) | Accuracy via θ |
| 5 MC | sample averages; weighted IS $W/C$ | Constant-α MC (6.1) for nonstationary |
| 6 TD | random walk TD α = 0.05–0.15 vs MC 0.01–0.04; windy α = 0.5; cliff α = 0.5 (Expected Sarsa fine at 1) | Batch TD answer independent of α |
| 7 n-step | best α shrinks as n grows (Fig 7.2) | n and α must be tuned together |
| 9 Approx. | 2×10⁻⁵ (gradient MC, 100k episodes), 10⁻⁴ / 5×10⁻⁵ (poly / Fourier), $1/(10n)$ tile coding | (9.19) rule of thumb |
2. Exploration parameters
| Parameter | Controls | Too small | Too large | Notes |
|---|---|---|---|---|
| ε (ε-greedy) | Fraction of random actions | Stuck on sub-optimal actions; slow discovery | Wasted steps; caps $P(\text{greedy})=1-\varepsilon+\varepsilon/k$; in cliff walking Q-learning falls off more | Decay (e.g. ε = 1/t) for GLIE convergence. On-policy MC/Sarsa converge to the best ε-soft policy for fixed ε |
| $Q_1$ (initial values) | Optimism ⇒ early exploration | No exploration bonus | Long initial exploration | Temporary; useless for nonstationary tasks; with −1 rewards, Q = 0 is already optimistic (windy gridworld) |
| $c$ (UCB) | Weight of the uncertainty bonus | ≈ greedy | Over-explores; spike/dip at step k+1 | Best ≈ 1–2 on the testbed |
| Baseline $\bar R_t$ | Variance of gradient-bandit updates | No effect on expected update; missing baseline with large rewards ⇒ slow | Running average of rewards | |
| Behaviour policy $b$ | Off-policy exploration | The more it differs from π, the larger IS ratios (variance) or shorter tree-backup spans | Must satisfy coverage | |
3. Discount rate γ
- Defines the problem: present value of a reward $k$ steps ahead is $\gamma^{k}$ (relative to the next reward). Effective horizon ≈ $1/(1-\gamma)$.
- γ = 0 myopic; γ → 1 far-sighted. Can change the optimal policy (Ex 3.22: left vs right flips at γ = 0.5).
- Needed (γ < 1) for continuing tasks to keep returns finite; episodic tasks may use γ = 1.
- DP convergence rate ∝ γ (contraction). Linear TD error bound $\frac{1}{1-\gamma}$ grows as γ → 1.
- Adding a constant $c$ to rewards adds $c/(1-\gamma)$ to all values (continuing) — but can change behaviour in episodic tasks.
4. Bootstrapping depth n (and σ)
| n | Method | Bias | Variance | Delay / memory |
|---|---|---|---|---|
| 1 | TD(0) | High (relies on V) | Low | None |
| intermediate | n-step TD | Medium | Medium | n steps, n transitions stored |
| ∞ | MC | None | High | Whole episode |
Intermediate n is usually best (Figs 7.2, 9.2), and the best α decreases as n increases. In Q(σ), σ = 1 samples (Sarsa-like, needs IS off-policy) and σ = 0 takes expectations (tree backup, no IS).
5. DP parameters
- θ: stop when the largest change in a sweep < θ. Policy iteration tolerates loose θ (greedy policy is often right early — Fig 4.1).
- Evaluation sweeps per improvement: 1 = value iteration, ∞ = policy iteration, between = truncated PI.
- Sweep order (in-place / asynchronous): strongly affects speed.
6. Function-approximation design choices
| Choice | Effect |
|---|---|
| Number of features $d$ / order $n$ | Resolution (acuity); polynomial and Fourier grow as $(n+1)^k$ |
| Receptive-field width (coarse coding) | Breadth of early generalisation; little effect on final accuracy |
| Tile width $w$, number of tilings $n$ | Resolution unit $w/n$; active features = $n$ ⇒ set $\alpha=1/(\tau n)$ |
| Tile offsets | Asymmetric (1, 3, 5, …) avoids diagonal artifacts; $n=2^m\ge4k$ |
| Tile shape | Stripes generalise along a dimension; conjunctive tiles learn interactions |
| RBF width σ | Smoothness / breadth |
| ε in LSTD | Too small ⇒ unstable inverses; too large ⇒ slow |
| Interest $I_t$ | Which states the objective cares about (emphasis $M_t$) |
7. How to read a parameter study
- Plot a summary of performance (e.g. average reward over the first 1000 steps, or RMS error over the first 10 episodes) against the parameter on a log scale (Figs 2.6, 6.3, 7.2, 9.2).
- Expect an inverted U (reward) or U (error): too small learns or explores too little; too large is noisy or unstable.
- Judge a method by its best value and by its sensitivity (width of the good region).
- Distinguish interim (early learning) from asymptotic performance — e.g. Sarsa's asymptotic return collapses at large α in cliff walking while Expected Sarsa's does not.