RL — Formula Sheet (CS1–CS7) — BITS Subject Vault

Every equation for the mid-sem, each with every symbol spelled out — bandits, returns, model dynamics, value functions, the Bellman equations, DP backups, and the Monte Carlo estimate. Pair with the slides explained.

Symbols

Symbol	Meaning
\(S_t, A_t, R_t\)	state, action, reward at step \(t\)
\(\pi(a\mid s)\)	policy: probability of action \(a\) in state \(s\)
\(G_t\)	return (cumulative future reward)
\(\gamma\)	discount rate, \(0 \le \gamma \le 1\)
\(\alpha\)	step size / learning rate
\(\varepsilon\)	exploration probability
\(q_*(a)\)	true value of bandit action \(a\)
\(Q_t(a)\)	estimated value of \(a\) at step \(t\)
\(v_\pi(s),\, q_\pi(s,a)\)	state-/action-value under policy \(\pi\)
\(v_(s),\, q_(s,a)\)	optimal state-/action-value
\(p(s',r\mid s,a)\)	model dynamics

Bandits

True action value

\[ q_*(a) \doteq \mathbb{E}[\,R_t \mid A_t = a\,] \]

The expected reward when action \(a\) is chosen. If every \(q_*(a)\) were known, you would just always pick \(\arg\max_a q_*(a)\).

Sample-average estimate

\[ Q_t(a) = \frac{\sum_{i=1}^{t-1} R_i \cdot \mathbb{1}_{A_i=a}}{\sum_{i=1}^{t-1} \mathbb{1}_{A_i=a}} \]

Average of the rewards actually received for \(a\). \(\mathbb{1}\) is the indicator (1 if true, else 0), so the numerator sums rewards on steps where \(a\) was taken and the denominator counts them.

Incremental update

\[ Q_{n+1} = Q_n + \alpha\,(R_n - Q_n) \]

NewEstimate \(\leftarrow\) OldEstimate \(+\) StepSize \(\cdot\) (Target \(-\) OldEstimate). With \(\alpha = \tfrac{1}{n}\) this is exactly the sample average; a constant \(\alpha\in(0,1]\) gives an exponentially-weighted (recency-biased) average for non-stationary problems.

Greedy & \(\varepsilon\)-greedy selection

\[ A_t = \arg\max_a Q_t(a) \qquad P(\text{greedy}) = 1 - \varepsilon + \tfrac{\varepsilon}{|\mathcal{A}|} \]

Greedy always exploits. \(\varepsilon\)-greedy explores a uniformly-random action with probability \(\varepsilon\); the greedy action can also be the random pick, hence the \(+\tfrac{\varepsilon}{|\mathcal{A}|}\) term.

Returns

Return (episodic)

\[ G_t = R_{t+1} + R_{t+2} + \dots + R_T \]

Sum of rewards to the final step \(T\) of an episode (game, maze run).

Discounted return (continuing)

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

\(\gamma\) sets the present value of future rewards: \(\gamma=0\) is myopic, \(\gamma\to 1\) is far-sighted. The recursion \(G_t = R_{t+1} + \gamma G_{t+1}\) is the seed of every Bellman equation.

Constant-reward sum

\[ \sum_{k=0}^{\infty} \gamma^k = \frac{1}{1-\gamma} \qquad (\gamma < 1) \]

A constant reward of \(+1\) every step gives a finite return when \(\gamma<1\).

Model dynamics

Dynamics function

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

The complete one-step model of the MDP. The Markov property: this depends only on the current \((s,a)\), not the history.

State-transition probability & expected reward

\[ p(s' \mid s,a) = \sum_{r} p(s',r \mid s,a) \qquad r(s,a,s') = \sum_{r} r\,\frac{p(s',r \mid s,a)}{p(s' \mid s,a)} \]

Marginalize the dynamics over reward to get the transition probability; the expected reward of a \((s,a,s')\) triple follows by conditioning.

Value functions

State- and action-value

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

\(v_\pi\) is the expected return from \(s\) following \(\pi\); \(q_\pi\) commits to action \(a\) first, then follows \(\pi\). They are linked by \(v_\pi(s)=\sum_a \pi(a\mid s)\,q_\pi(s,a)\).

Bellman equations

Bellman expectation (for policy \(\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] \]

Value of a state = average over the policy's actions of (immediate reward \(+\) discounted value of the next state). Self-consistency is what makes value computable.

Bellman optimality

\[ 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) \]

The only change from the expectation form is \(\max_a\) instead of averaging over \(\pi\) — take the best action. Solving it yields the optimal policy directly.

Dynamic programming backups

Policy evaluation (iterate to convergence)

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

Turn the Bellman expectation equation into an assignment and sweep all states until \(v\) stops changing — converges to \(v_\pi\).

Policy improvement

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

Act greedily w.r.t. \(v_\pi\). The policy improvement theorem guarantees \(\pi'\) is no worse than \(\pi\).

Value iteration

\[ v(s) \leftarrow \max_a \sum_{s',r} p(s',r\mid s,a)\big[\,r + \gamma\,v(s')\,\big] \]

One Bellman optimality backup per sweep — converges to \(v_*\); then read off the greedy policy.

Monte Carlo

First-/every-visit estimate

\[ v_\pi(s) \approx \frac{1}{N}\sum_{i=1}^{N} G_i^{(s)} \qquad Q(s,a) \leftarrow Q(s,a) + \tfrac{1}{N}\big(G - Q(s,a)\big) \]

Replace the expectation with an empirical average of the returns \(G_i\) actually observed after visiting \(s\) (or \((s,a)\)) across sampled episodes. Model-free, episodic.

Off-policy importance-sampling ratio

\[ \rho_{t:T-1} = \prod_{k=t}^{T-1} \frac{\pi(A_k\mid S_k)}{b(A_k\mid S_k)} \]

Reweights returns gathered under behaviour policy \(b\) to estimate the target policy \(\pi\) — the ratio of how likely each was to produce the trajectory.

Read it as one chain. Define the return \(G_t\) \(\rightarrow\) take its expectation to get value \(v_\pi\) \(\rightarrow\) expand the recursion to get Bellman \(\rightarrow\) turn Bellman into a backup to get DP \(\rightarrow\) replace the expectation with a sample average to get Monte Carlo.

RL formula sheet — every equation, every symbol defined.