RL — Cheatsheet (CS1–CS7) — BITS Subject Vault

Dense, scannable revision card for CS1–CS7: every definition, equation, algorithm box, comparison table, worked mini-example, and exam gotcha in one place. Read top-to-bottom the night before; understand it from the slides explained and prove each equation on the formula sheet.

The big picture — five lectures, one arc

RL learns a policy (what to do) from a reward signal by interacting with an environment — no labels, delayed feedback. The mid-sem builds in five moves: bandits isolate explore/exploit (no states); MDPs add states and formalize sequential decisions; the Bellman equations relate value-now to value-next; DP solves a known MDP; Monte Carlo learns an unknown one from sampled episodes.

Lec	Topic	Key move
CS1	Intro & elements	agent/env loop; policy, reward, value, model
CS2–3	Bandits	\(\varepsilon\)-greedy; \(Q\leftarrow Q+\alpha(R-Q)\)
CS3–5	MDPs & Bellman	\(p(s',r\mid s,a)\); \(v_\pi,q_\pi\); Bellman eqs
CS4–6	Dynamic programming	policy iteration, value iteration (GPI)
CS6–7	Monte Carlo	average sampled returns (model-free)

Vocabulary you must know cold

Term	Symbol	Meaning
Agent	—	The learner / decision-maker.
Environment	—	Everything outside the agent (limit of its control, not knowledge).
State	\(S_t\)	The situation; must be Markov (summarizes the past).
Action	\(A_t\)	What the agent does.
Reward	\(R_t\)	Scalar feedback from the environment; defines the goal.
Return	\(G_t\)	Cumulative (discounted) future reward — what we maximize.
Policy	\(\pi(a\mid s)\)	State → action-probabilities; the thing we learn.
State value	\(v_\pi(s)\)	Expected return from \(s\) under \(\pi\).
Action value	\(q_\pi(s,a)\)	Expected return after \(a\) in \(s\), then \(\pi\).
Model	\(p\)	Predicts next state & reward; optional (model-based vs free).
Discount	\(\gamma\)	Present value of future reward, \(0\le\gamma\le1\).
Step size	\(\alpha\)	Learning rate.
Exploration rate	\(\varepsilon\)	Probability of a random action.

Three confusions examiners love. (1) Reward vs value: reward is immediate, value is long-run expected reward — a low-reward state can have high value. (2) RL is not a neural network; it's a learning approach (deep RL just uses NNs inside it). (3) Policy vs value: the policy is behaviour; the value function grades it.

RL vs supervised vs unsupervised

—	Supervised	Unsupervised	Reinforcement
Feedback	Correct label (instructive)	None	Reward score (evaluative)
Objective	\(p(y\mid x)\)	\(p(x)\)	\(\pi(a\mid s)\) — a policy
Data	Labelled	Unlabelled	Experience from interaction
Algo	SVM, KNN, reg.	K-means, Apriori	Q-learning, SARSA

CS2–3 — multi-armed bandits

One state, \(k\) actions, reward from a fixed distribution per action. Goal: maximize expected total reward — the pure explore/exploit problem.

\[ q_*(a)=\mathbb{E}[R_t\mid A_t=a] \qquad Q_t(a)=\frac{\sum_{i

Incremental update (no need to store rewards):

\[ Q_{n+1}=Q_n+\alpha(R_n-Q_n) \qquad \alpha=\tfrac1n \Rightarrow \text{sample average} \]

Selection: greedy \(A_t=\arg\max_a Q_t(a)\) exploits; \(\varepsilon\)-greedy explores a uniform-random action with prob. \(\varepsilon\) and converges (every arm sampled \(\infty\) often).

Tweak	What & why
Constant \(\alpha\)	Exponential recency-weighted average → tracks nonstationary bandits.
Optimistic init	High \(Q_1\) → all actions disappoint → free early exploration (stationary only).
UCB	\(A_t=\arg\max_a[Q_t(a)+c\sqrt{\ln t / N_t(a)}]\) — explore by uncertainty.
Gradient bandit	Soft-max over learned preferences \(H_t(a)\); previews policy gradient.

Ex-1 (memorize the method). Two actions, \(\varepsilon=0.5\): \(P(\text{greedy})=1\cdot(1-\varepsilon)+\tfrac12\varepsilon=0.5+0.25=0.75\). On a random step the greedy arm still has a \(\tfrac12\) chance of being drawn — that's the \(+0.25\).

CS3–5 — MDPs & returns

An MDP = (states, actions, dynamics, reward, \(\gamma\)). Everything sits in one function, the dynamics:

\[ p(s',r\mid s,a)=\Pr\{S_t=s',R_t=r\mid S_{t-1}=s,A_{t-1}=a\} \]

Markov property: next state/reward depend only on current \((s,a)\), not history. Derived: \(p(s'\mid s,a)=\sum_r p(s',r\mid s,a)\).

\[ G_t=\sum_{k=0}^{\infty}\gamma^k R_{t+k+1}=R_{t+1}+\gamma G_{t+1} \qquad \sum_{k=0}^\infty\gamma^k=\tfrac{1}{1-\gamma} \]

Episodic (ends at \(T\)) vs continuing (\(T=\infty\), needs \(\gamma<1\)). Reward hypothesis: goals = maximizing expected cumulative reward; reward the what, not the how (chess: reward winning, not capturing pieces).

\[ v_\pi(s)=\mathbb{E}_\pi[G_t\mid S_t=s] \qquad q_\pi(s,a)=\mathbb{E}_\pi[G_t\mid S_t=s,A_t=a] \]

Bellman equations

Expectation (value-now via value-next, averaged over \(\pi\)):

\[ v_\pi(s)=\sum_a\pi(a\mid s)\sum_{s',r}p(s',r\mid s,a)\big[r+\gamma v_\pi(s')\big] \]

Optimality (take the best action instead of averaging):

\[ v_*(s)=\max_a\sum_{s',r}p(s',r\mid s,a)\big[r+\gamma v_*(s')\big] \qquad \pi_*(s)=\arg\max_a q_*(s,a) \]

Why we can't just solve it. The Bellman optimality equation needs (1) a known model \(p\), (2) enough compute for all states, (3) the Markov property. Real problems break at least one — hence DP (known model) and Monte Carlo (no model).

CS4–6 — dynamic programming (known model)

Method	Update	Output
Policy evaluation	\(v(s)\leftarrow\sum_a\pi\sum p[r+\gamma v(s')]\), sweep to converge	\(v_\pi\)
Policy improvement	\(\pi'(s)=\arg\max_a\sum p[r+\gamma v_\pi(s')]\)	policy \(\ge\) old (theorem)
Policy iteration	evaluate \(\rightleftarrows\) improve	optimal \(\pi_*\) (finite steps)
Value iteration	\(v(s)\leftarrow\max_a\sum p[r+\gamma v(s')]\), once/sweep	\(v_\) → greedy \(\pi_\)

Value Iteration:
  init V(s)=0
  repeat:
    for each s:  V(s) ← max_a Σ p(s',r|s,a)[ r + γ V(s') ]
  until V stops changing
  π(s) = argmax_a Σ p(s',r|s,a)[ r + γ V(s') ]

GPI (generalized policy iteration): evaluation ⇄ improvement at any granularity → both converge on the optimum. DP bootstraps (updates estimates from other estimates) and needs full sweeps (curse of dimensionality).

CS6–7 — Monte Carlo (unknown model)

Learn from sampled episodes — average the actual returns. Model-free, episodic only, no bootstrapping.

\[ v_\pi(s)\approx\text{average of returns after visiting } s \]

First-visit MC: average returns after the first visit to \(s\) per episode. Every-visit: after every visit.
No model ⇒ estimate action values \(q_\pi(s,a)\) (state values alone can't give a policy without \(p\)).
Maintain exploration so all \((s,a)\) get sampled: exploring starts | on-policy \(\varepsilon\)-soft | off-policy.
Off-policy: act with behaviour \(b\), learn target \(\pi\); reweight by importance ratio \(\rho=\prod \pi(A_k\mid S_k)/b(A_k\mid S_k)\).

DP vs MC (classic exam contrast)

—	DP	Monte Carlo
Model	Needs full \(p\)	None — experience only
Bootstrap	Yes	No (full returns)
Update	Every sweep	End of episode
Tasks	Any (with model)	Episodic only
Variance	Low (exact backup)	Higher (sampled returns)

Last-minute gotchas

MoE of this subject: size MDP value off the recursion — almost every equation is "reward + \(\gamma\)·next value."
Bellman optimality = Bellman expectation with max replacing the policy average. That single swap is worth marks.
Constant \(\alpha\) does not converge (it tracks change); \(\tfrac1n\) does. Convergence needs \(\sum\alpha_n=\infty,\ \sum\alpha_n^2<\infty\).
Greedy on \(v_*\) is optimal because \(v_*\) already accounts for all future rewards.
MC waits for the episode to end; that's why it needs episodic tasks and has higher variance.

Rest of the vault

Slides Explained · the concepts in full
Formula Sheet · every symbol defined
Question Bank · test yourself
Book Explained · Sutton & Barto Ch 1–5, deep

RL cheatsheet — the whole mid-sem, cram-ready.