Skip to content
CampusPrep
CS-601 · Machine Learning/Quick Revision Short Notes

Machine Learning (CS-601) - Unit 4 Short Notes

How unit 4 is examined

Sequence models (RNN, LSTM, GRU, translation, BLEU, attention) and reinforcement learning (RL framework, MDP, Bellman, value and policy iteration, actor-critic, Q-learning, SARSA); the marks sit in RNN, LSTM, MDP, value vs policy iteration, actor-critic and Q-learning/SARSA.

Recurrent neural network

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>A recurrent neural network (RNN) is a neural network with feedback connections that processes sequential data by keeping a hidden state which carries information from earlier time steps to later ones.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-01" viewBox="0 0 510 338" width="510" height="338" role="img" aria-label="RNN unfolded in time. x_t input, h_t hidden state, y_t output. The same weights U, W, V are reused at every step. Folded form: one hidden unit with a loop arrow back to itself."><style>#dsfig-u4-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-01 .t{fill:#16181D;font-weight:500}#dsfig-u4-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-01 .dot{fill:#16181D}#dsfig-u4-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-01 .ah{fill:#454C5A}#dsfig-u4-01 .ah.hi{fill:#2340B8}#dsfig-u4-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-01 .e{stroke:#B1B7C3}html.dark #dsfig-u4-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-01 .t{fill:#E6E8ED}html.dark #dsfig-u4-01 .t.inv{fill:#0F1115}html.dark #dsfig-u4-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-01 .dot{fill:#E6E8ED}html.dark #dsfig-u4-01 .ann{fill:#8FA3FF}html.dark #dsfig-u4-01 .lbl{fill:#858D9C}html.dark #dsfig-u4-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-01 .ah{fill:#B1B7C3}html.dark #dsfig-u4-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M126,279 L126,190" marker-end="url(#ah6)"/><path class="e" d="M298,279 L298,190" marker-end="url(#ah6)"/><path class="e" d="M470,279 L470,190" marker-end="url(#ah6)"/><path class="e" d="M59,169 L105,169" marker-end="url(#ah6)"/><path class="e" d="M145,169 L277,169" marker-end="url(#ah6)"/><path class="e" d="M317,169 L449,169" marker-end="url(#ah6)"/><path class="e" d="M126,150 L126,61" marker-end="url(#ah6)"/><path class="e" d="M298,150 L298,61" marker-end="url(#ah6)"/><path class="e" d="M470,150 L470,61" marker-end="url(#ah6)"/><circle class="n" cx="126" cy="298" r="18"/><text class="t" x="126" y="298" dy=".35em" text-anchor="middle">x1</text><circle class="n" cx="298" cy="298" r="18"/><text class="t" x="298" y="298" dy=".35em" text-anchor="middle">x2</text><circle class="n" cx="470" cy="298" r="18"/><text class="t" x="470" y="298" dy=".35em" text-anchor="middle">x3</text><circle class="n" cx="40" cy="169" r="18"/><text class="t" x="40" y="169" dy=".35em" text-anchor="middle">h0</text><circle class="n" cx="126" cy="169" r="18"/><text class="t" x="126" y="169" dy=".35em" text-anchor="middle">h1</text><circle class="n" cx="298" cy="169" r="18"/><text class="t" x="298" y="169" dy=".35em" text-anchor="middle">h2</text><circle class="n" cx="470" cy="169" r="18"/><text class="t" x="470" y="169" dy=".35em" text-anchor="middle">h3</text><circle class="n" cx="126" cy="40" r="18"/><text class="t" x="126" y="40" dy=".35em" text-anchor="middle">y1</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">y2</text><circle class="n" cx="470" cy="40" r="18"/><text class="t" x="470" y="40" dy=".35em" text-anchor="middle">y3</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">RNN unfolded in time. x_t input, h_t hidden state, y_t output. The same weights U, W, V are reused at every step. Folded form: one hidden unit with a loop arrow back to itself.</figcaption></figure>

Key points.

  1. At every time step the RNN reads the input $x_t$ and the previous hidden state $h_{t-1}$ and produces a new state, so the state acts as memory of the sequence so far.
  2. The state update is $h_t=\tanh(Wh_{t-1}+Ux_t+b)$ and the output is $y_t=Vh_t+c$.
  3. The same weights $U,W,V$ are shared across all time steps, so the number of parameters does not grow with sequence length and the network handles inputs of any length.
  4. It is trained by backpropagation through time (BPTT), which unfolds the loop and backpropagates the error through every step.
  5. Because BPTT multiplies many gradients, a vanilla RNN suffers from vanishing gradients (long-term dependencies are lost) or exploding gradients (fixed by gradient clipping).
  6. It is suitable wherever order matters: speech recognition, text and next-word prediction, machine translation, time-series forecasting and video frames.

Types of architecture. Vanilla RNN: simple hidden state, weak on long sequences. LSTM: gated memory cell for long-term dependencies. GRU: simplified LSTM with fewer parameters. By input/output shape: one-to-many (image captioning), many-to-one (sentiment), many-to-many (translation).

Comparison.

Feed-forward network RNN
Acyclic; data flows one way Cyclic; hidden state feeds back
No memory; each input is independent Memory through hidden state
Fixed-size static input Variable-length sequences
Separate weights per layer Same weights reused per time step
Trained by ordinary backpropagation Trained by BPTT
Images, tabular data Text, speech, time series
Vanilla RNN LSTM
--- ---
No gates, suffers vanishing gradient Three gates plus cell state
Fewest parameters Most parameters
Short memory Best long memory

Answer frame. Open with the definition; draw the folded and unfolded diagram; develop points 1-6; close with suitable cases (speech, text). For the comparison question give both tables and end with "gates solve the vanishing gradient of vanilla RNN".

Asked: [7 marks] (Dec 2020) What do you mean by Recurrent neural network? Explain with the help of a diagram. In which cases this model is suitable. Asked: [7 marks] (May 2023) Structural and operational differences between a feed-forward network and an RNN; differences between LSTM, GRU and vanilla RNNs. Asked: [7 marks] (May 2024) Define Recurrent Neural Networks (RNNs). Explain the types of architecture of an RNN.

Long short-term memory

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>LSTM is a gated recurrent unit with a separate cell state whose gates decide what to forget, what to store and what to output, so it can learn long-term dependencies.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-02" viewBox="0 0 596 295" width="596" height="295" role="img" aria-label="LSTM cell. F forget gate, I input gate, G candidate memory, O output gate, C cell state c_t, ht hidden state. Inputs to every gate are x_t and h_{t-1}."><style>#dsfig-u4-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-02 .t{fill:#16181D;font-weight:500}#dsfig-u4-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-02 .dot{fill:#16181D}#dsfig-u4-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-02 .ah{fill:#454C5A}#dsfig-u4-02 .ah.hi{fill:#2340B8}#dsfig-u4-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-02 .e{stroke:#B1B7C3}html.dark #dsfig-u4-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-02 .t{fill:#E6E8ED}html.dark #dsfig-u4-02 .t.inv{fill:#0F1115}html.dark #dsfig-u4-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-02 .dot{fill:#E6E8ED}html.dark #dsfig-u4-02 .ann{fill:#8FA3FF}html.dark #dsfig-u4-02 .lbl{fill:#858D9C}html.dark #dsfig-u4-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-02 .ah{fill:#B1B7C3}html.dark #dsfig-u4-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M55.8,244.5 L151.5,180.6" marker-end="url(#ah7)"/><path class="e" d="M58,249 L278.1,175.6" marker-end="url(#ah7)"/><path class="e" d="M58.5,250.9 L406.5,173.6" marker-end="url(#ah7)"/><path class="e" d="M58.7,251.9 L535.3,172.5" marker-end="url(#ah7)"/><path class="e" d="M182.4,155.6 L283.2,54.8" marker-end="url(#ah7)"/><path class="e" d="M298,150 L298,61" marker-end="url(#ah7)"/><path class="e" d="M413.6,155.6 L312.8,54.8" marker-end="url(#ah7)"/><path class="e" d="M317,40 L535,40" marker-end="url(#ah7)"/><path class="e" d="M556,150 L556,61" marker-end="url(#ah7)"/><circle class="n" cx="40" cy="255" r="18"/><text class="t" x="40" y="255" dy=".35em" text-anchor="middle">xt</text><circle class="n" cx="169" cy="169" r="18"/><text class="t" x="169" y="169" dy=".35em" text-anchor="middle">F</text><circle class="n" cx="298" cy="169" r="18"/><text class="t" x="298" y="169" dy=".35em" text-anchor="middle">I</text><circle class="n" cx="427" cy="169" r="18"/><text class="t" x="427" y="169" dy=".35em" text-anchor="middle">G</text><circle class="n" cx="556" cy="169" r="18"/><text class="t" x="556" y="169" dy=".35em" text-anchor="middle">O</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="556" cy="40" r="18"/><text class="t" x="556" y="40" dy=".35em" text-anchor="middle">ht</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">LSTM cell. F forget gate, I input gate, G candidate memory, O output gate, C cell state c_t, ht hidden state. Inputs to every gate are x_t and h_{t-1}.</figcaption></figure>

Equations.

$$f_t=\sigma(W_f[h_{t-1},x_t]+b_f),\quad i_t=\sigma(W_i[h_{t-1},x_t]+b_i),\quad o_t=\sigma(W_o[h_{t-1},x_t]+b_o)$$ $$\tilde c_t=\tanh(W_c[h_{t-1},x_t]+b_c),\quad c_t=f_t\odot c_{t-1}+i_t\odot\tilde c_t,\quad h_t=o_t\odot\tanh(c_t)$$

Key points.

  1. The cell state $c_t$ runs along the whole sequence with only small linear updates, so information and gradients flow across many steps without vanishing.
  2. The forget gate outputs values between 0 and 1 and decides how much of the old cell state $c_{t-1}$ to keep.
  3. The input gate together with the candidate $\tilde c_t$ decides which new information is written into the cell state.
  4. The cell state is updated by forgetting part of the old memory and adding the gated new memory, as in the $c_t$ equation.
  5. The output gate decides how much of $\tanh(c_t)$ is exposed as the hidden state $h_t$, which is passed to the next step and to the output layer.
  6. Sigmoid gates act as valves (0 = block, 1 = pass), which is how gating controls long-term dependencies.

Answer frame. Open with the definition; draw the cell with three gates; write the six equations; explain gates in order forget, input, output; close with "gating solves vanishing gradient and keeps long-term memory".

Asked: [7 marks] (Dec 2024, Jun 2025) Explain the architecture of an LSTM unit and how it processes sequential data by controlling the flow of information through various gates. Discuss the structure of Long Short Term Memory.

Gated recurrent unit

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. A GRU is a simplified LSTM that merges the cell and hidden state and uses only two gates.

Key points.

  1. The update gate $z_t=\sigma(W_z[h_{t-1},x_t])$ decides how much of the old state to keep, like forget and input gates combined.
  2. The reset gate $r_t=\sigma(W_r[h_{t-1},x_t])$ decides how much of the past to ignore when forming the candidate $\tilde h_t=\tanh(W[r_t\odot h_{t-1},x_t])$.
  3. The new state is $h_t=(1-z_t)\odot h_{t-1}+z_t\odot\tilde h_t$.
  4. It has fewer parameters than LSTM, so it trains faster with similar accuracy.

Translation

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Machine translation converts text from a source language to a target language, usually with a sequence-to-sequence (seq2seq) model.

Key points.

  1. The encoder (an RNN or LSTM) reads the source sentence and compresses it into a context vector.
  2. The decoder generates the target words one at a time, each conditioned on the context vector and the previous word.
  3. A single fixed-size context vector loses information on long sentences, which is why attention was introduced.
  4. Output is chosen by greedy or beam search and scored with BLEU.

Beam search and width

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Beam search is a decoding method that keeps the $B$ most probable partial sentences at every step instead of only the single best word; $B$ is the beam width.</mark>

Key points.

  1. At each step every kept sentence is extended with all candidate words, and only the $B$ highest-scoring (highest total log-probability) sequences survive.
  2. Beam width 1 is greedy search; a larger width searches more of the space and gives better translations but costs more time and memory.
  3. Scores use $\sum\log P(y_t\mid y_{<t},x)$, usually length-normalised so that long sentences are not unfairly penalised.
  4. Search stops when the best beams end with the end-of-sentence token.

Bleu score

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>BLEU (bilingual evaluation understudy) scores a machine translation by its n-gram precision against reference translations, multiplied by a brevity penalty.</mark>

Formula. $$\text{BLEU}=BP\cdot\exp\Big(\sum_{n=1}^{4}w_n\log p_n\Big),\quad BP=\begin{cases}1 & c>r\\ e^{1-r/c} & c\le r\end{cases}$$

Key points.

  1. n-gram precision $p_n$ is the fraction of n-grams (words or phrases) of the candidate that appear in the reference, so it rewards correct word choice; 1-gram to 4-gram precisions are combined by a geometric mean with $w_n=1/4$.
  2. The brevity penalty (c = candidate length, r = reference length) penalises translations shorter than the reference, because a very short output could otherwise get high precision.
  3. Together they balance correctness with proper length; the score lies between 0 and 1 (or 0-100).
  4. Example: $c=4,r=5$ gives $BP=e^{-0.25}=0.779$.

Asked: [7 marks] (May 2024) Describe the significance of n-gram precision and brevity penalty in the BLEU score calculation.

Attention model

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Attention lets the decoder look at all encoder states and focus on the most relevant ones at each output step, instead of using one fixed context vector.

Key points.

  1. For each decoder step scores $e_{ti}$ are computed between the decoder state and every encoder state $h_i$, and softmax turns them into weights $\alpha_{ti}$.
  2. The context vector is the weighted sum $c_t=\sum_i\alpha_{ti}h_i$, which changes at every output word.
  3. In the transformer, self-attention is $\text{softmax}(QK^T/\sqrt{d_k})V$ and needs no recurrence, so it runs in parallel.
  4. It fixes the long-sentence bottleneck of plain seq2seq.

Reinforcement Learning

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Reinforcement learning is learning by interaction, in which an agent takes actions in an environment and learns a policy that maximises the cumulative reward it receives.</mark>

Key points.

  1. The agent is the learner and decision maker; the environment is everything it interacts with.
  2. A state $s$ describes the current situation, and an action $a$ is the agent's choice in that state.
  3. The reward $r$ is the scalar feedback after an action; it may be delayed, so the agent must learn which earlier actions were responsible.
  4. The policy $\pi(a\mid s)$ maps states to actions and is what the agent learns.
  5. The return is the discounted sum $G_t=r_{t+1}+\gamma r_{t+2}+\dots$ with $0\le\gamma\le1$, and the value function $V^\pi(s)=E[G_t\mid s]$ is the expected return from a state.
  6. Exploration (trying new actions) versus exploitation (using the best known action) must be balanced, for example by epsilon-greedy.
  7. There are no labelled examples, unlike supervised learning; applications are games (AlphaGo), robotics, self-driving cars and recommendation.

Answer frame. Open with the definition and the agent-environment loop; then develop elements 1-5, then exploration vs exploitation; close with examples (game playing, robot walking).

Asked: [7 marks] (May 2022, Dec 2024) What is Reinforcement learning? Explain its detailed concepts. Define Reinforcement Learning (RL). Explain its elements in detail.

RL framework

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>The RL framework is a closed loop in which, at each step, the agent observes state $s_t$, takes action $a_t$, and the environment returns reward $r_{t+1}$ and next state $s_{t+1}$.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-03" viewBox="0 0 348.5 80" width="348.5" height="80" role="img" aria-label="Agent-environment loop. The agent sends action a_t; the environment replies with state s_{t+1} and reward r_{t+1}."><style>#dsfig-u4-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-03 .t{fill:#16181D;font-weight:500}#dsfig-u4-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-03 .dot{fill:#16181D}#dsfig-u4-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-03 .ah{fill:#454C5A}#dsfig-u4-03 .ah.hi{fill:#2340B8}#dsfig-u4-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-03 .e{stroke:#B1B7C3}html.dark #dsfig-u4-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-03 .t{fill:#E6E8ED}html.dark #dsfig-u4-03 .t.inv{fill:#0F1115}html.dark #dsfig-u4-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-03 .dot{fill:#E6E8ED}html.dark #dsfig-u4-03 .ann{fill:#8FA3FF}html.dark #dsfig-u4-03 .lbl{fill:#858D9C}html.dark #dsfig-u4-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-03 .ah{fill:#B1B7C3}html.dark #dsfig-u4-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M68.6,47.1 Q169,72 277.6,45.1" marker-end="url(#ah8)"/><path class="e" d="M279.6,35.4 Q169,8 70.6,32.4" marker-end="url(#ah8)"/><g class="wl"><rect x="136.7" y="50" width="68.7" height="18" rx="9"/><text class="t" x="171.1" y="59" dy=".35em" text-anchor="middle">action_a</text></g><g class="wl"><rect x="109.8" y="12" width="124.5" height="18" rx="9"/><text class="t" x="172" y="21" dy=".35em" text-anchor="middle">state_s,reward_r</text></g><rect class="n" x="11.5" y="25" width="57" height="30" rx="15"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">Agent</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">Env</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Agent-environment loop. The agent sends action a_t; the environment replies with state s_{t+1} and reward r_{t+1}.</figcaption></figure>

Key points.

  1. The goal is to find the policy that maximises expected cumulative discounted reward, $\max_\pi E[\sum_t\gamma^t r_t]$.
  2. The framework is formalised as a Markov Decision Process (S, A, P, R, $\gamma$).
  3. The loop repeats until a terminal state or forever (continuing task).
  4. Agent components are the policy, the value function and optionally a model of the environment.
  5. Example: in chess the state is the board, the action is a move and the reward is +1 for win, -1 for loss.

Answer frame. Open with the definition; draw the loop; list state, action, policy, reward; state the goal; close with an example. For the MDP-and-Bellman variant, continue into the next two sections.

Asked: [7 marks] (Dec 2020) Explain the concept of Reinforcement Learning and its framework in details. Asked: [7 marks] (Jun 2026) Explain the Reinforcement Learning framework, Markov Decision Process (MDP) and Bellman equations.

MDP

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>A Markov Decision Process is the tuple $(S,A,P,R,\gamma)$ that models sequential decision making where the next state depends only on the current state and action.</mark>

Key points.

  1. S is the set of states and A the set of actions available to the agent.
  2. $P(s'\mid s,a)$ is the transition probability of reaching $s'$ after taking action $a$ in state $s$.
  3. $R(s,a,s')$ is the reward received on that transition, and $\gamma\in[0,1]$ discounts future rewards.
  4. Markov property: $P(s_{t+1}\mid s_t,a_t,\dots,s_0)=P(s_{t+1}\mid s_t,a_t)$, so the present state summarises the whole history.
  5. A policy $\pi(a\mid s)$ says which action to take; the goal is the optimal policy $\pi^*$ with the highest value $V^*(s)$ in every state.
  6. Working: the agent is in $s$, picks $a$, the environment samples $s'$ and gives $r$, and this repeats; the value functions follow the Bellman equations.
  7. MDP gives RL its mathematical form, and solvers are value iteration and policy iteration.

Answer frame. Open with the definition; list the tuple S, A, P, R; state the Markov property; explain policy and value; close with Bellman equations and a grid-world example.

Asked: [7 marks] (May 2022, Jun 2025) Describe the concept of MDP. Explain the working principle of Markov Decision Process in detail.

Bellman equations

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Bellman equations express the value of a state as the immediate reward plus the discounted value of the next state.</mark>

Key points.

  1. Expectation equation for a policy: $V^\pi(s)=\sum_a\pi(a\mid s)\sum_{s'}P(s'\mid s,a)[R+\gamma V^\pi(s')]$.
  2. Optimality equation: $V^*(s)=\max_a\sum_{s'}P(s'\mid s,a)[R+\gamma V^*(s')]$.
  3. For action values: $Q^*(s,a)=\sum_{s'}P(s'\mid s,a)[R+\gamma\max_{a'}Q^*(s',a')]$.
  4. They are the basis of policy evaluation, value iteration and Q-learning.

Value Iteration and Policy Iteration

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Both are dynamic-programming algorithms that find the optimal policy of a known MDP using the Bellman equations.</mark>

Steps.

Value iteration:
Step 1: Initialise V(s)=0 for all states.
Step 2: Repeat V(s) = max_a sum P(s'|s,a)[R + gamma V(s')] for every state.
Step 3: Stop when the largest change is below a threshold.
Step 4: Extract policy pi(s) = argmax_a sum P(s'|s,a)[R + gamma V(s')].
Policy iteration:
Step 1: Start with an arbitrary policy.
Step 2: Policy evaluation: solve V^pi for the current policy.
Step 3: Policy improvement: pi(s) = argmax_a of the one-step lookahead on V^pi.
Step 4: Repeat Steps 2-3 until the policy stops changing.

Comparison.

Point Value iteration Policy iteration
Idea Update values with the Bellman optimality max Alternate evaluation and improvement
Starts with Arbitrary values Arbitrary policy
Policy Extracted once at the end Explicit policy at every iteration
Cost per iteration Cheap (one sweep) Expensive (full evaluation)
Iterations Many Few
Convergence Values converge in the limit Policy converges in finite steps
Best for Large state spaces Small spaces needing exact policy

Example. Grid-world with reward 1 per move, $\gamma=0.9$, $V_0=0$: after sweep 1, $V=1$ for cells next to the goal; sweep 2 spreads $1+0.9\cdot1=1.9$ one cell further. Policy iteration reaches the same optimum in fewer, costlier rounds.

Answer frame. Open with the shared aim; write both algorithms as steps; give the comparison table; close with the grid-world example. For the MDP add-on, define the MDP tuple (see MDP).

Asked: [7 marks] (Dec 2020) Explain the difference between Value iteration and Policy iteration. What is Markov Decision Process (MDP)? Asked: [7 marks] (Dec 2024, Jun 2026) Explain the difference between Value Iteration and Policy Iteration algorithms. Compare them with suitable examples.

Actor-critic model

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Actor-critic is an RL method that combines a policy-based actor, which selects actions, with a value-based critic, which evaluates them.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-04" viewBox="0 0 352.5 252" width="352.5" height="252" role="img" aria-label="Actor takes actions, the environment gives state and reward, the critic computes the TD error and sends it to the actor."><style>#dsfig-u4-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-04 .t{fill:#16181D;font-weight:500}#dsfig-u4-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-04 .dot{fill:#16181D}#dsfig-u4-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-04 .ah{fill:#454C5A}#dsfig-u4-04 .ah.hi{fill:#2340B8}#dsfig-u4-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-04 .e{stroke:#B1B7C3}html.dark #dsfig-u4-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-04 .t{fill:#E6E8ED}html.dark #dsfig-u4-04 .t.inv{fill:#0F1115}html.dark #dsfig-u4-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-04 .dot{fill:#E6E8ED}html.dark #dsfig-u4-04 .ann{fill:#8FA3FF}html.dark #dsfig-u4-04 .lbl{fill:#858D9C}html.dark #dsfig-u4-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-04 .ah{fill:#B1B7C3}html.dark #dsfig-u4-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah9" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh9" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M68,116.7 L278.1,46.6" marker-end="url(#ah9)"/><path class="e" d="M298,59 L298,176.5" marker-end="url(#ah9)"/><path class="e" d="M266.2,201.4 L69.9,136" marker-end="url(#ah9)"/><g class="wl"><rect x="141.9" y="74" width="54.3" height="18" rx="9"/><text class="t" x="169" y="83" dy=".35em" text-anchor="middle">action</text></g><g class="wl"><rect x="281.2" y="117" width="33.6" height="18" rx="9"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">s,r</text></g><g class="wl"><rect x="138.3" y="160" width="61.5" height="18" rx="9"/><text class="t" x="169" y="169" dy=".35em" text-anchor="middle">TDerror</text></g><rect class="n" x="11.5" y="111" width="57" height="30" rx="15"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">Actor</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">Env</text><rect class="n" x="265.5" y="197" width="65" height="30" rx="15"/><text class="t" x="298" y="212" dy=".35em" text-anchor="middle">Critic</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Actor takes actions, the environment gives state and reward, the critic computes the TD error and sends it to the actor.</figcaption></figure>

Key points.

  1. The actor is a policy network $\pi_\theta(a\mid s)$ that outputs a probability distribution over actions.
  2. The critic estimates the value function $V(s)$ (expected cumulative reward) and judges how good the visited state is.
  3. Interaction: the actor acts, the environment returns $r$ and $s'$, and the critic computes the TD error $\delta=r+\gamma V(s')-V(s)$.
  4. The critic is updated to shrink $\delta$, and the actor is updated by $\theta\leftarrow\theta+\alpha\,\delta\,\nabla_\theta\log\pi_\theta(a\mid s)$, so good actions become more probable.
  5. Advantages: lower variance than pure policy gradient, faster and more stable convergence, and natural handling of continuous actions.
  6. Compared with value-only methods (Q-learning) it learns a stochastic policy directly; compared with policy-only methods it learns online each step, not at episode end.

Answer frame. Open with the definition; draw the loop; explain actor, critic, then the TD error link; list advantages; close with A2C/A3C as examples. For the Q-learning/SARSA variant add one line each from the next two sections.

Asked: [7 marks] (Dec 2020, May 2024) Explain the Actor critic model. List its advantages in reinforcement learning. Explain the roles of the actor and critic networks and how they interact. Asked: [7 marks] (Jun 2026) Explain Actor-Critic, Q-Learning and SARSA algorithms.

Q-learning

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Q-learning is a model-free, off-policy temporal-difference algorithm that learns the action-value function $Q(s,a)$, the expected return of taking action $a$ in state $s$ and then acting optimally.</mark>

Formula. $$Q(s,a)\leftarrow Q(s,a)+\alpha\big[r+\gamma\max_{a'}Q(s',a')-Q(s,a)\big]$$ In the deterministic case ($\alpha=1$): $Q(s,a)\leftarrow r+\gamma\max_{a'}Q(s',a')$.

Steps.

Step 1: Initialise the Q-table Q(s,a) to 0.
Step 2: Observe the current state s.
Step 3: Choose a by epsilon-greedy on Q and execute it.
Step 4: Observe reward r and next state s'.
Step 5: Update Q(s,a) with the formula above.
Step 6: Set s = s'; repeat until the episode ends, over many episodes.

Key points.

  1. Model-free means the agent learns from experienced $(s,a,r,s')$ without knowing $P$ or $R$; model-based learning first learns or is given the model and then plans (value iteration is model-based).
  2. It is off-policy because the update uses the greedy $\max_{a'}$ even though the behaviour policy explores.
  3. Q-values converge to $Q^*$ if every state-action pair is visited infinitely often and the learning rate decays.
  4. With deterministic rewards and actions, the update drops $\alpha$ and each Q entry only increases towards its true value.
  5. Example: $Q=0,r=1,\gamma=0.9,\max Q(s',\cdot)=5,\alpha=0.5$ gives $Q=0+0.5(1+4.5-0)=$ 2.75.

Comparison.

Model-based Model-free (Q-learning)
Uses or learns $P$ and $R$ Learns directly from experience
Plans (value/policy iteration) Trial and error
Sample-efficient, needs a model Simple, needs more samples

Answer frame. Open with the definition; give the formula and steps; state off-policy and convergence; close with the numerical. For the model-based question lead with the table.

Asked: [8 marks] (Jun 2025) What is Model based and model free learning Q-Learning? Explain. Asked: [7 marks] (Dec 2020) Describe Q-learning in brief. What is SARSA algorithm? Explain this. Asked: [7 marks] (May 2022) Explain Q learning algorithm assuming deterministic rewards and actions.

SARSA

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>SARSA is an on-policy temporal-difference algorithm named after the tuple $(s,a,r,s',a')$, updating Q with the action actually taken next.</mark>

Formula. $$Q(s,a)\leftarrow Q(s,a)+\alpha\big[r+\gamma Q(s',a')-Q(s,a)\big]$$

Key points.

  1. $a'$ is chosen by the same epsilon-greedy policy that is being learned, so SARSA is on-policy.
  2. Q-learning uses $\max_{a'}$ (off-policy), so it learns the optimal path; SARSA learns a safer path that accounts for exploration.
  3. Same example as Q-learning with $Q(s',a')=4$: $Q=0.5(1+3.6)=$ 2.3.
  4. Use SARSA when exploration mistakes are costly; both need a Q-table and exploration.

Last-minute revision

  • RNN: $h_t=\tanh(Wh_{t-1}+Ux_t+b)$, weights shared across time, trained by BPTT.
  • Vanilla RNN has vanishing or exploding gradients; LSTM and GRU fix it with gates.
  • LSTM has forget, input and output gates and a cell state: $c_t=f_t c_{t-1}+i_t\tilde c_t$, $h_t=o_t\tanh(c_t)$.
  • GRU has reset and update gates, no cell state, fewer parameters.
  • Beam width 1 is greedy search; BLEU = brevity penalty times geometric mean of 1-4 gram precisions.
  • MDP = (S, A, P, R, $\gamma$) with the Markov property.
  • Bellman optimality: $V^*(s)=\max_a\sum P[R+\gamma V^*(s')]$.
  • Value iteration updates values then extracts the policy; policy iteration alternates evaluation and improvement.
  • Actor = policy, critic = value; the TD error $r+\gamma V(s')-V(s)$ trains both.
  • Q-learning (off-policy) uses $\max Q(s',a')$; SARSA (on-policy) uses $Q(s',a')$.
  • Worked update: $\alpha=0.5,\gamma=0.9,r=1,\max Q=5$ gives 2.75.

Memory hooks

  • LSTM gates FIO: Forget, Input, Output.
  • GRU = Get Rid of Useless (reset, update): two gates.
  • SARSA spells the tuple s, a, r, s', a': on-policy; Q-learning takes the Quickest max.
  • Actor acts, critic criticises.
  • Value iteration = values first, policy last; policy iteration = policy first, always.

Coverage checklist

  • Recurrent neural network: Dec 2020 diagram, May 2023 comparison, May 2024 types.
  • Long short-term memory: Dec 2024 / Jun 2025 architecture.
  • gated recurrent unit: covered, also in the RNN comparison.
  • translation: covered.
  • beam search and width: covered.
  • Bleu score: May 2024 n-gram precision and brevity penalty.
  • attention model: covered.
  • Reinforcement Learning: May 2022 / Dec 2024.
  • RL-framework: Dec 2020, Jun 2026.
  • MDP: May 2022 / Jun 2025, and the Dec 2020 MDP part.
  • Bellman equations: covered, Jun 2026 part.
  • Value Iteration and Policy Iteration: Dec 2020, Dec 2024 / Jun 2026.
  • Actor-critic model: Dec 2020 / May 2024, Jun 2026.
  • Q-learning: Dec 2020, May 2022, Jun 2025.
  • SARSA: covered, Dec 2020 and Jun 2026 parts.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in