RL slides explained — CS1 to CS7, in plain easy words.

Every mid-sem lecture deck (CS1–CS7) of Deep Reinforcement Learning, rewritten slide-by-slide in plain language — full concepts, the why behind each idea, with the course's own examples (slot machines, the recycling robot, the noisy grid world). The arc: what RL is and its building blocks → multi-armed bandits and the explore/exploit dilemma → Markov decision processes → returns, value functions and the Bellman equations → dynamic programming → Monte Carlo methods. Textbook: Sutton & Barto, 2nd ed.

CS1 — what reinforcement learning is

CS1 · course intro + introducing RL

Reinforcement learning (RL) is reward-based / feedback-based learning. An agent learns by interacting with an environment: it tries actions, sees what happens, and gets a numerical reward signal telling it how good that was. Over many tries it learns to act so as to collect the most reward over time. The course's one-line definition (Gartner's): RL rewards desired behaviours and punishes undesired ones — instead of one input giving one fixed output, the algorithm produces many possible outputs and is trained to pick the right one.

Crucially, RL is not a type of neural network nor an alternative to one. It is an approach to learning. (Deep RL just means we use neural networks as the tools inside that approach.) Typical uses: autonomous driving, game playing, robotics, healthcare.

RL vs supervised vs unsupervised learning

The three learning paradigms differ in what signal they get:

Criteria	Supervised	Unsupervised	Reinforcement
Learns from	Labelled data	Unlabelled data	Interacting with the environment
Data	Labelled	Unlabelled	No predefined data
Problem	Regression, classification	Association, clustering	Exploitation or exploration
Objective	\(p(y\mid x)\)	\(p(x)\)	\(\pi(a\mid s)\) — a policy
Aim	Calculate outcomes	Find patterns	Learn a series of actions
Algorithms	Linear/logistic reg., SVM, KNN	K-means, Apriori	Q-learning, SARSA

Notice the RL objective is a policy \(\pi(a\mid s)\) — a rule for choosing actions in states — not a label or a density. And RL gets no supervision: only a reward signal that may arrive late.

When to use RL

RL fits large environments in three situations: (1) a model of the environment is known but no analytic solution exists; (2) only a simulation model is given (simulation-based optimization); (3) the only way to gather information is to interact with the environment. The unifying theme: goal-oriented learning from interaction.

The agent–environment loop

This single picture is the spine of the whole course. At each time step the agent senses the state, picks an action, and the environment returns a reward and the next state. The agent's utility is the sum of rewards; it should learn to act so as to maximize expected reward, learning purely from observed action outcomes.

The elements of an RL system

Beyond the agent and environment, four sub-elements define an RL system:

• Policy — the agent's behaviour: a mapping from states to actions (or to probabilities of actions). The thing we ultimately want to learn.
• Reward signal — the immediate, short-term goal: a number the environment hands back each step. Defines what is good now.
• Value function — the long-term goal: how much total reward to expect from a state onward. Good immediate reward ≠ high value, and vice versa.
• Model (optional) — the agent's idea of how the environment behaves (what next state and reward follow an action). Model-based methods use it; model-free methods don't.

And the basic vocabulary, illustrated by a child learning to ride a bicycle: the agent is the entity learning (the child); an action (A) is what it does each step (pedal, steer); the state (S) is the current situation (position, balance); the reward (R) is feedback after an action; the environment is the outside world it operates in. Formal definition: RL is the area of machine learning concerned with how intelligent agents ought to take actions in an environment so as to maximize cumulative reward.

Characteristics of RL

Four traits make RL its own beast: no supervision, only a reward signal; decisions are sequential (one choice affects all that follow); time matters; and feedback is delayed, not instant — the consequence of a move may only show up much later. That delay (the "credit assignment" problem) is what makes RL hard and interesting.

CS2–CS3 — multi-armed bandits

CS2–CS3 · k-armed bandits, action-value methods, explore/exploit

Before full RL we study a stripped-down problem that isolates the hardest idea — explore vs exploit — with no states to worry about: the k-armed bandit. You face k options (think k slot machines / "one-armed bandits"). Repeatedly you pick one and receive a numerical reward drawn from a fixed (stationary) probability distribution that depends only on which arm you pulled. Objective: maximize expected total reward over some time period.

Action value \(q_*(a)\)

Each arm has a true value — its expected reward when selected:

If you knew every \(q_*(a)\), the problem would be trivial: always pull the arm with the highest value. The catch: you don't know them. You only have estimates \(Q_t(a)\), which you must build up from the rewards you actually see. Notation: \(A_t\) = action chosen at step \(t\); \(Q_t(a)\) = estimated value of \(a\) at step \(t\); \(q_*(a)\) = its true value.

Estimating values: the sample-average method

The natural estimate is to average the rewards actually received for that arm:

Worked example from the slides: pull arm a three times, getting \(-1, -1, 5\) → estimate \(Q(a) = \tfrac{-1-1+5}{3} = 1\). Arm b gives \(-0.2, -0.2\) → \(Q(b) = -0.2\); and so on. Keep pulling, keep updating the estimates. The key subtlety the slides highlight: an arm that looks inferior so far might actually be the best — your estimates are noisy, especially early.

Greedy and \(\varepsilon\)-greedy action selection

Given estimates, how do you choose? Greedy selection always takes the arm with the highest current estimate:

But pure greed never tries the others, so it can get stuck on a wrong early estimate — that's the exploration vs exploitation dilemma: exploit what looks best now, or explore to improve your estimates for later. The fix is \(\varepsilon\)-greedy (near-greedy): behave greedily most of the time, but with small probability \(\varepsilon\) pick a random arm.

epsilon = 0.05            # small exploration probability
def get_action():
    if random.random() > epsilon:
        return argmax_a(Q(a))     # exploit
    else:
        return random.choice(A)   # explore

Why it works: in the limit of infinite steps, \(\varepsilon\)-greedy samples every arm infinitely often, so every estimate \(Q_t(a)\) converges to the true \(q_*(a)\). It's easy to implement, easy to tune (just \(\varepsilon\)), and yields good results.

Incremental update (don't store all rewards)

Re-averaging from scratch every step wastes memory. Rewrite the average as an incremental update: new estimate = old estimate + step-size × (reward − old estimate).

general:  NewEstimate \(\leftarrow\) OldEstimate \(+\) StepSize \(\cdot\) (Target \(-\) OldEstimate)

The bracket (Target − OldEstimate) is the error; you nudge the estimate toward the new reward by a step size. With step size 1/n this exactly reproduces the running average.

Non-stationary problems

If the bandit's true values drift over time (non-stationary), a plain average is wrong — it weights ancient rewards as heavily as recent ones. Use a constant step size \(\alpha\) instead of \(\tfrac1n\):

This makes the estimate an exponentially weighted average that forgets old rewards — recent experience counts more. The right choice for a changing world.

Optimistic initial values & the 10-armed testbed

How you initialize the estimates matters. Setting them optimistically high encourages early exploration: every arm disappoints relative to the rosy initial guess, so the agent keeps trying others until reality sets in — exploration for free, without \(\varepsilon\). To compare methods fairly the slides use the 10-armed testbed: 2000 randomly generated 10-armed bandit problems, true values drawn from a \(\mathcal{N}(0,1)\), each pull's reward \(\mathcal{N}(q_*(a), 1)\). Run a method 1000 steps per problem, average over the 2000 runs to see its typical behaviour.

Smarter exploration — UCB

\(\varepsilon\)-greedy explores blindly: when it explores it picks any action equally, even obviously bad ones. Upper-Confidence-Bound (UCB) selection explores by uncertainty instead — it favours actions that are either promising or under-sampled:

\(N_t(a)\) is how many times \(a\) has been chosen, and \(c>0\) tunes exploration. The square-root term is a measure of uncertainty: each time \(a\) is picked, \(N_t(a)\) grows and the term shrinks (we are surer); each time a different action is picked, \(t\) grows but \(N_t(a)\) does not, so \(a\)'s bonus slowly rises until it gets retried. UCB often beats \(\varepsilon\)-greedy on stationary bandits but is harder to extend to large state spaces.

Learning preferences — gradient bandits

A different idea: instead of estimating values, learn a numerical preference \(H_t(a)\) for each action and choose by a soft-max:

Preferences are nudged up for actions that beat a running baseline (the average reward so far) and down otherwise, by stochastic gradient ascent. The preference has no meaning as a reward — only relative preferences matter. This is the first taste of policy-gradient methods, which act on a parameterized policy directly rather than through value estimates — a major theme after the mid-sem.

What the testbed actually shows

Running these methods on the 10-armed testbed gives the chapter's punchline: greedy improves fastest at the very start but plateaus low, because it locks onto an early favourite and never corrects. \(\varepsilon=0.1\) explores a lot and finds the best arm quickly but keeps making 10% random moves forever; \(\varepsilon=0.01\) learns slower but eventually overtakes it. The lesson: some exploration almost always beats none, and the right amount depends on the noise — noisier rewards reward more exploration, near-deterministic rewards reward greed.

CS3–CS5 — Markov decision processes

CS3–CS5 · the agent–environment interface, MDPs, returns, value functions, Bellman

Bandits had no states. Real problems do: your action changes the situation, which changes which actions are good next. The framework for that is the Markov Decision Process (MDP) — the formal model of sequential decision making. The interaction unfolds in discrete steps as a stream: S₀, A₀, R₁, S₁, A₁, R₂, … with the objective to maximize the return (cumulative reward) over time.

Grid world — the running example

The slides' maze-like grid world makes MDPs concrete. The agent lives in a grid; walls block it. Movement is noisy: action "North" goes North only 80% of the time; 10% it veers West, 10% East; if a wall is in the way it stays put. Rewards: −0.1 per step (battery drain), +1 for reaching (4,3), −1 for reaching (4,2). Goal: maximize accumulated reward. The noise is the point — actions don't always do what you intend, so you must plan around uncertainty.

What defines an MDP

An MDP is specified by:

• a set of states S;
• a set of actions A;
• state-transition probabilities — the chance of landing in s′ after doing a in s (also called the model dynamics);
• a reward function — the utility from a transition;
• a start state, and maybe a terminal state.

The full dynamics are captured by one function:

From it you get the state-transition probability \(p(s'\mid s,a) = \sum_r p(s',r\mid s,a)\) and the expected reward \(r(s,a,s')\). The Markov property is the key assumption: the next state and reward depend only on the current state and action — not the full history. The present state summarizes everything that matters.

The MDP framework is abstract and flexible

Time steps need not be real-time intervals; actions can be low-level controls or high-level decisions, even mental/computational ones; states can be raw sensations or abstract symbolic descriptions. The agent–environment boundary marks the limit of the agent's absolute control, not of its knowledge. The slides' framing: any problem of goal-directed learning reduces to three signals — actions (the choices), states (the basis for choices), and rewards (the goal).

The recycling robot (detailed example)

A robot collects cans, runs on a battery, and must decide how to search based on charge. It's a complete worked MDP:

• States: S = {high, low} (battery charge).
• Actions: A(high) = {search, wait}; A(low) = {search, wait, recharge}.
• Rewards: zero most of the time except when a can is secured; searching earns more than waiting (r_search > r_wait); running out of charge and needing rescue costs −3.

The transition table encodes the dynamics: searching on high stays high with probability α (reward r_search) or drops to low with 1−α; searching on low stays low with β or depletes (rescued to high) with 1−β at reward −3; waiting keeps the state with reward r_wait; recharge from low returns to high at reward 0. This table is the MDP — states, actions, probabilities, rewards, all in one place.

The reward hypothesis (and how to get it wrong)

The slides state the reward hypothesis: all of what we mean by goals and purposes can be thought of as maximizing the expected cumulative sum of a received scalar signal (the reward). The vital caveat: rewards should say what you want achieved, not how. Two cautionary tales — reward a chess agent for capturing pieces and it may walk into traps to grab material; reward a vacuum per unit of dirt collected and it may dump dirt out just to re-suck it. Reward the goal, never the sub-steps.

Returns and episodes

The goal is to maximize the return \(G_t\) — some function of the future reward sequence. Two task types:

• Episodic tasks have a natural end (a final step \(T\)): a game, a trip through a maze. Return = sum of rewards to the end: \(G_t = R_{t+1} + R_{t+2} + \dots + R_T\).
• Continuing tasks go on forever (T = ∞). A plain sum could be infinite, so we discount.

\(\gamma\) sets the present value of future rewards: \(\gamma=0\) is myopic (only the next reward matters); \(\gamma\to 1\) is far-sighted. A beautiful recursion falls out — the return obeys \(G_t = R_{t+1} + \gamma G_{t+1}\) — which is the seed of every Bellman equation to come. And for a constant reward of \(+1\) with \(\gamma<1\) the infinite sum is finite: \(\sum_k \gamma^k = \tfrac{1}{1-\gamma}\).

Policy and value functions

A policy \(\pi(a\mid s)\) is a mapping from states to probabilities over actions — the agent's behaviour. Learning means improving \(\pi\) from experience. To judge a policy we use two value functions:

State-value \(v_\pi(s)\): how good is state \(s\) under \(\pi\). Action-value \(q_\pi(s,a)\): how good is taking \(a\) in \(s\), then following \(\pi\).

v_π(s) is the expected return starting from s and following π forever; q_π(s,a) is the same but you commit to action a first. The grid-world picture of "values after 100 iterations" (numbers in each cell rising toward the +1 goal) is exactly v_π being computed.

The Bellman equations

Plug the recursion \(G_t = R_{t+1} + \gamma G_{t+1}\) into the value definition and you get the Bellman expectation equation — value today expressed in terms of value tomorrow:

In words: the value of a state is the average over the actions the policy might take, of (immediate reward + discounted value of where you land). This self-consistency is what makes RL computable: instead of summing infinite futures, you relate each value to its neighbours. The optimal value functions \(v_*(s)\) and \(q_*(s,a)\) are the best achievable over all policies, and they satisfy the Bellman optimality equation:

The only change from the expectation form: replace "average over the policy's actions" with "take the best action." Solve this and the optimal policy is simply: in each state, pick the action that achieves the max.

CS4–CS6 — dynamic programming

CS4–CS6 · solving a known MDP: policy & value iteration

If you know the MDP (the full dynamics p), you can solve it exactly by dynamic programming (DP) — turning the Bellman equations into update rules you iterate until they stop changing. DP is model-based and the conceptual backbone for everything model-free that follows.

Policy evaluation (the prediction problem)

Given a fixed policy π, how good is it — what is v_π? Iterative policy evaluation just turns the Bellman expectation equation into an assignment and sweeps it over all states, again and again:

repeat:
  for each state s:
     v(s) ← Σ_a π(a|s) Σ_{s′,r} p(s′,r|s,a) [ r + γ v(s′) ]
until v stops changing (Δ < θ)

Each sweep makes the estimate more accurate; it provably converges to the true v_π. This is the grid-world "values after N iterations" animation made into an algorithm.

Policy improvement

Now that you know v_π, can you do better? Yes: in each state, act greedily with respect to v_π — pick the action with the best (reward + discounted next value). The policy improvement theorem guarantees this new greedy policy is at least as good as the old one, strictly better unless the old one was already optimal.

Policy iteration

Alternate the two steps and you climb to the optimum: evaluate → improve → evaluate → improve … Each round gives a strictly better policy; since a finite MDP has finitely many policies, this reaches the optimal policy in finite time.

Value iteration

Policy evaluation can be slow (many sweeps to fully evaluate before improving). Value iteration shortcuts it: do a single Bellman optimality backup per state per sweep — fold evaluation and improvement into one update:

repeat:
  for each state s:
     v(s) ← max_a Σ_{s′,r} p(s′,r|s,a) [ r + γ v(s′) ]
until v stops changing; then read off the greedy policy

It converges to \(v_*\) directly, then the optimal policy is the greedy policy w.r.t. \(v_*\). The unifying idea behind both algorithms is Generalized Policy Iteration (GPI): let evaluation and improvement interact, in any granularity, and they converge together on the optimal value function and policy.

The algorithms, as pseudocode

Both DP methods are short loops over the state set. Policy evaluation sweeps the expectation backup until values stop moving; value iteration sweeps the optimality backup instead:

Policy Evaluation (for v_π):           Value Iteration (for v_*):
  init V(s)=0                            init V(s)=0
  repeat:                                repeat:
    for each s:                            for each s:
      V(s) ← Σ_a π(a|s) ·                    V(s) ← max_a
        Σ p(s',r|s,a)[r + γ V(s')]              Σ p(s',r|s,a)[r + γ V(s')]
  until max change < θ                   until max change < θ
  return V ≈ v_π                         return greedy policy w.r.t. V

The only difference is the \(\max_a\) versus the \(\sum_a\pi(a\mid s)\) — the same swap that turns the Bellman expectation equation into the optimality equation. Both update in place (one array, overwrite as you go), which uses fresh values immediately and converges faster.

A tiny worked sweep

Take two states \(A,B\) with \(\gamma=0.9\). Suppose from \(A\) the best action gives reward \(0\) and lands in \(B\) for sure, and \(B\) is terminal with value \(0\) but the action that reaches it earns \(+10\). One value-iteration sweep with \(V_0(A)=V_0(B)=0\): \(V_1(B)=\max(\cdot)=10\) (the terminal-reaching action), then \(V_1(A)=0+0.9\cdot V_0(B)=0\); next sweep \(V_2(A)=0+0.9\cdot V_1(B)=0.9\cdot10=9\). The value of \(B\)'s payoff "backs up" one state per sweep until \(V(A)=9\) stabilizes. That spreading of value outward from reward is exactly the grid-world animation made numeric.

CS6–CS7 — Monte Carlo methods

CS6–CS7 · learning from experience, no model needed

What if you don't know the MDP's dynamics? Monte Carlo (MC) methods learn directly from experience — sampled episodes of states, actions, and rewards — with no model at all. The idea is simple and powerful: to estimate the value of a state, run episodes and average the returns actually observed from that state. MC only applies to episodic tasks (you need episodes that end so the return is well-defined).

Monte Carlo prediction

Recall v_π(s) is the expected return from s. MC replaces "expected" with "empirical average": play out many episodes under π, and for each visit to state s record the return that followed; average them.

• First-visit MC: average the return following only the first time s is visited in each episode.
• Every-visit MC: average the return after every visit to s.

Both converge to v_π(s) as the number of visits grows — by the law of large numbers, the sample mean approaches the true mean. The contrast with DP is the whole lesson: DP computed values from a known model by backups; MC learns them from sampled experience, model-free.

Estimating action values

Without a model you can't turn v into a policy (you'd need p to look ahead). So MC estimates action values q_π(s,a) directly — average the returns following each (state, action) pair. The danger: if the policy never tries some action in some state, you never get a return for it and can't estimate it. The fix is to guarantee every state–action pair gets sampled.

Monte Carlo control: exploring starts

MC control (finding the best policy) follows the same GPI loop as DP — evaluate, then improve greedily — but using MC estimates of q. To make sure every action is tried, one device is exploring starts: begin each episode at a random state–action pair so, in the limit, all of them are sampled. Then alternate: estimate q from episodes, improve the policy to be greedy w.r.t. q, repeat. It converges to the optimal policy.

On-policy and off-policy MC

Exploring starts is often impractical (you can't always reset to an arbitrary state–action). Two realistic alternatives:

• On-policy MC — keep the policy soft (\(\varepsilon\)-greedy: every action has at least \(\varepsilon/|\mathcal{A}|\) probability) so exploration is built in. You evaluate and improve the same policy you act with, edging it toward the best \(\varepsilon\)-soft policy.
• Off-policy MC — act with an exploratory behaviour policy but learn about a different target policy (often the greedy optimal one). Because the data came from a different distribution, you reweight returns with importance sampling — the ratio of how likely the target vs behaviour policy was to produce that trajectory.

Importance sampling, a little deeper

Off-policy learning needs to estimate returns under the target policy \(\pi\) from episodes generated by a different behaviour policy \(b\). The trick is to reweight each return by how much more (or less) likely its trajectory was under \(\pi\) than under \(b\) — the importance-sampling ratio:

Beautifully, the environment's unknown transition probabilities appear identically in numerator and denominator and cancel — so \(\rho\) depends only on the two policies and the actions taken, never on the model. The coverage assumption is required: any action \(\pi\) might take must be possible under \(b\) (\(\pi(a\mid s)>0\Rightarrow b(a\mid s)>0\)). There are two ways to average the reweighted returns: ordinary IS (divide by the number of episodes) is unbiased but can have enormous variance; weighted IS (divide by the sum of the \(\rho\)'s) is slightly biased but far lower variance, and is what you use in practice.

The thread through CS1–CS7

Step back and the mid-sem is one continuous argument:

Lecture	Question it answers	Key tool
CS1	What is RL? What are its parts?	Agent–environment loop; policy/reward/value/model
CS2–3	How to balance explore vs exploit?	k-armed bandit; \(\varepsilon\)-greedy; incremental update
CS3–5	How to model sequential decisions?	MDP; return; value functions; Bellman equations
CS4–6	How to solve a known MDP?	DP: policy iteration, value iteration (GPI)
CS6–7	How to learn without a model?	Monte Carlo: average sampled returns

Each lecture removes an assumption the previous one needed: bandits drop states, MDPs add them back, DP assumes you know the model, MC throws the model away. By the mid-sem you can model a problem as an MDP, reason about its values with Bellman, solve it exactly when you have the model, and estimate it from experience when you don't — the complete classical-RL toolkit, and the foundation deep RL is built on.

References

• RL — Book Explained (Sutton & Barto Ch 1–5) · the same ideas, chapter by chapter
• RL — Cheatsheet · every equation and skeleton on one card
• RL — Question Bank · test yourself, no answers
• Sutton & Barto — Reinforcement Learning: An Introduction (2e) · the textbook, free PDF
• David Silver — UCL RL course · the canonical lecture series