Reinforcement Learning

Full Unit-wise Notes for Exam Preparation | RL Framework, Bandits, MDPs, Bellman Equations, DP,
MC, TD, Q-Learning, Function Approximation, DQN, Policy Gradient, HRL, Options, POMDP

How to use these notes: First finish definitions and formulas. Then practise algorithms and difference tables. For
14-mark answers, use the format: introduction, diagram/framework, equation/algorithm, explanation, example,
advantages, limitations, conclusion.

Syllabus Map
Unit Main topics covered in these notes

Unit I Introduction to RL, RL framework, applications, bandits, exploration-exploitation, UCB, PAC, median
elimination, Thompson sampling, contextual bandits, returns, value functions, MDPs, policy search and
REINFORCE basics.

Unit II MDP modelling, Bellman equation, Bellman optimality equation, Banach fixed point theorem, contraction
and convergence idea, value iteration, policy iteration, dynamic programming, Monte Carlo, off-policy
MC, UCT, TD(0), TD control, Q-learning.

Unit III Eligibility traces, backward view, TD(lambda), function approximation, linear approximation, state
aggregation, LSTD, LSTDQ, LSPI, fitted Q, DQN, policy gradient, actor-critic, REINFORCE with function
approximation.

Unit IV Hierarchical RL, types of optimality, semi-Markov decision process, options, learning with options, HAM,
MAXQ, option discovery, POMDP introduction, solving POMDP.

Quick Formula Sheet

Return: G_t = R_{t+1} + gamma R_{t+2} + gamma^2 R_{t+3} + ...
State value: V_pi(s) = E_pi[G_t | S_t = s]
Action value: Q_pi(s,a) = E_pi[G_t | S_t = s, A_t = a]
Bellman V: V_pi(s) = sum_a pi(a|s) sum_{s',r} p(s',r|s,a)[r + gamma V_pi(s')]
Bellman Q: Q_pi(s,a) = sum_{s',r} p(s',r|s,a)[r + gamma sum_{a'} pi(a'|s')Q_pi(s',a')]
Optimal V: V*(s) = max_a sum_{s',r} p(s',r|s,a)[r + gamma V*(s')]
Optimal Q: Q*(s,a) = sum_{s',r} p(s',r|s,a)[r + gamma max_{a'} Q*(s',a')]
TD(0): V(S_t) <- V(S_t) + alpha[R_{t+1} + gamma V(S_{t+1}) - V(S_t)]
SARSA: Q(S,A) <- Q(S,A) + alpha[R + gamma Q(S',A') - Q(S,A)]
Q-learning: Q(S,A) <- Q(S,A) + alpha[R + gamma max_{a}Q(S',a) - Q(S,A)]
REINFORCE: theta <- theta + alpha G_t grad log pi_theta(A_t|S_t)

Important Terminology
Term Meaning

Agent Learner or decision maker. It observes state, takes action, receives reward and improves
policy.

Environment External system with which the agent interacts. It returns next state and reward.

State Representation of current situation. It should contain enough information for decision
making.

Action Choice made by the agent.

Reinforcement Learning Full Notes Page 1

 Term Meaning

Reward Immediate numerical feedback signal. RL maximizes long-term cumulative reward, not
only immediate reward.

Policy Mapping from states to actions. It may be deterministic or stochastic.

Value function Expected return from a state or state-action pair under a policy.

Model Description of transition probabilities and rewards. Model-based RL uses it; model-free
RL learns without it.

Episode A complete sequence from start state to terminal state.

Discount factor gamma in [0,1]. It controls importance of future rewards.

Reinforcement Learning Full Notes Page 2

 UNIT I - Basics of RL and Bandits
1. Introduction to Reinforcement Learning
Reinforcement Learning (RL) is a branch of machine learning in which an agent learns how to behave by
interacting with an environment. The agent is not given direct correct answers. Instead, it receives rewards or
penalties and learns a policy that maximizes long-term return.

The central idea is trial and error learning. The agent tries actions, observes consequences, and improves future
decisions. RL is useful when decisions are sequential and the effect of an action may be visible after many steps.

Core characteristics
- Sequential decision making: current actions affect future states and future rewards.

- Delayed reward: the best action may not give immediate reward but may produce high future reward.

- Exploration: the agent must try uncertain actions to discover better choices.

- Exploitation: the agent uses the best action known so far.

- Learning from experience: training data is generated by the agent itself while interacting with the environment.

RL compared with supervised and unsupervised learning

Point Supervised Learning Unsupervised Learning Reinforcement Learning

Data Labelled input-output pairs Unlabelled data Experience from interaction

Feedback Correct label is given No direct label Reward signal is given

Goal Predict label/output Find patterns/clusters Maximize cumulative reward

Decision type Mostly one-step prediction Pattern discovery Sequential decisions

Example Spam classification Customer clustering Robot navigation

2. RL Framework
The RL framework contains an agent and an environment. At time t, the agent receives state S_t, selects action A_t
according to policy pi, receives reward R_{t+1}, and moves to next state S_{t+1}. This loop continues until
termination or indefinitely.
S_t -> Agent chooses A_t -> Environment returns R_{t+1}, S_{t+1}
Goal: learn a policy pi that maximizes expected return E[G_t].

Elements of RL
- State space S: all possible states.

- Action space A: all possible actions.

- Reward function R: gives reward after action.

- Transition function P: probability of next state given current state and action.

- Policy pi: strategy used by the agent.

- Discount factor gamma: controls future reward importance.

- Value function V or Q: evaluates goodness of states/actions.

Simple example
In a grid-world problem, the agent is a robot, states are grid cells, actions are up/down/left/right, reward may be +10
for reaching goal and -1 per step. The agent learns a policy that reaches the goal quickly.

Reinforcement Learning Full Notes Page 3

 3. Applications of RL
- Robotics: path planning, grasping objects, walking robots.

- Games: chess, Go, Atari games, strategy games.

- Self-driving vehicles: lane changing, speed control, decision making.

- Recommendation systems: long-term user engagement rather than one-click prediction.

- Networking: routing, congestion control, resource allocation.

- Finance: portfolio management and trading strategies.

- Healthcare: treatment planning and dosage control, with strict safety constraints.

- Industrial control: energy optimization, production scheduling, inventory control.

4. Exploration vs Exploitation
Exploration means trying actions that are not known well. Exploitation means choosing the action that currently
appears best. A good RL agent balances both. Too much exploration wastes reward; too much exploitation may
trap the agent in a suboptimal action.

Aspect Exploration Exploitation

Meaning Try uncertain or new actions Use best known action

Benefit Discovers better options Gives high immediate reward

Risk May choose bad actions May miss better actions

Example Try a new route Use usual fastest route

5. Multi-Armed Bandits
A multi-armed bandit is the simplest RL problem. There is only one state and several actions, called arms. Each
arm gives rewards from an unknown probability distribution. The goal is to maximize total reward or minimize regret
over repeated trials.
At each time t:
1. choose action/arm A_t
2. receive reward R_t
3. update estimate of action value Q(A_t)

Action-value estimate
Q_t(a) = estimated value of action a = average of rewards received after selecting a
Incremental update:
Q_{new}(a) = Q_{old}(a) + alpha [R - Q_{old}(a)]

Regret
Regret measures the loss due to not always choosing the optimal arm. If q*(a*) is the expected reward of the best
arm, regret after T steps is the difference between reward of always selecting a* and the actual reward obtained.
Expected regret: Regret(T) = T q*(a*) - E[sum_{t=1}^{T} R_t]

6. Value Function Based Methods for Bandits

Sample-average method
The sample-average method estimates the value of an action by averaging rewards received from that action. It is
simple and works well for stationary problems.
Q_t(a) = (R_1 + R_2 + ... + R_{N_t(a)}) / N_t(a)

Reinforcement Learning Full Notes Page 4

 Epsilon-greedy method
In epsilon-greedy, the agent chooses the best estimated action with probability 1 - epsilon and chooses a random
action with probability epsilon. It is easy to implement and ensures continuous exploration.

- Small epsilon gives more exploitation.

- Large epsilon gives more exploration.

- Epsilon may be reduced over time to shift from exploration to exploitation.

Optimistic initial values

All action values are initialized with high values. The agent tries each action because untried actions look
promising. It encourages exploration without using random action selection every time.

Softmax/Boltzmann exploration
Softmax selects actions probabilistically based on their estimated values. Better actions get higher probability, but
lower-valued actions still have some chance.
P(A=a) = exp(Q(a)/tau) / sum_b exp(Q(b)/tau)
Tau is temperature. High tau -> more random, low tau -> more greedy.

7. Concentration Bounds and UCB

Concentration bounds show how close a sample average is to the true mean with high probability. In bandits, they
help decide which action has high uncertainty and should be explored.

Hoeffding inequality idea

For bounded independent rewards, the sample mean becomes close to the true mean as number of samples
increases. This gives an upper confidence interval around each action-value estimate.
Confidence width roughly = sqrt( (2 log t) / N_t(a) )

UCB - Upper Confidence Bound

UCB selects the action with the highest optimistic value. It adds an exploration bonus to the estimated reward.
Actions selected fewer times have larger bonus and are explored.
A_t = argmax_a [ Q_t(a) + c sqrt( log t / N_t(a) ) ]

UCB1 formula
A_t = argmax_a [ Q_t(a) + sqrt( (2 ln t) / N_t(a) ) ]

The first term exploits high estimated reward. The second term explores uncertain actions. As N_t(a) increases,
uncertainty decreases.

UCB1 theorem - exam idea

For stochastic bandits with bounded rewards, UCB1 achieves logarithmic regret in time T. This means the number
of times a suboptimal arm is selected grows only logarithmically with T, which is much better than linear regret.

- UCB does not need a fixed epsilon.

- It explores based on uncertainty.

- It is suitable when rewards are stationary and bounded.

- It may be less suitable for non-stationary environments unless modified.

8. PAC Bounds and Median Elimination

PAC means Probably Approximately Correct. In bandits, a PAC algorithm returns an action whose expected reward
is within epsilon of the optimal action with probability at least 1 - delta.
PAC guarantee: P( q*(a_returned) >= q*(a*) - epsilon ) >= 1 - delta

Reinforcement Learning Full Notes Page 5

 Median Elimination algorithm
Median elimination is a pure exploration algorithm. Its goal is to identify an epsilon-optimal arm with high probability
while using a limited number of samples.

Steps
- Start with all arms as active arms.

- Sample each active arm enough times to estimate its mean.

- Compute median of estimated means.

- Remove arms whose estimated mean is below the median.

- Reduce epsilon and delta parameters and repeat.

- Continue until only one arm remains.

Key points
- It eliminates about half of the arms in each round.

- It gives PAC style correctness guarantee.

- It focuses on finding a good arm, not maximizing reward during learning.

- It is useful for best-arm identification problems.

9. Thompson Sampling
Thompson sampling is a Bayesian exploration method. It maintains a probability distribution over the unknown
reward of each action. At each step, it samples a possible value from each action distribution and selects the action
with the highest sampled value.

Beta-Bernoulli bandit example

If rewards are 0 or 1, each arm can be modeled with a Beta distribution. For each arm, alpha counts successes and
beta counts failures.
For each arm a: sample theta_a from Beta(alpha_a, beta_a)
Choose arm with largest theta_a
If reward = 1: alpha_a <- alpha_a + 1
If reward = 0: beta_a <- beta_a + 1

Advantages
- Naturally balances exploration and exploitation.

- Uses uncertainty directly.

- Often performs very well in practice.

- Can be extended to contextual bandits and complex models.

Limitations
- Needs a probability model/prior.

- May be difficult for complex reward distributions.

- Approximate sampling may be needed in large problems.

10. Contextual Bandits

In contextual bandits, before selecting an action the agent observes context or features. The best action may
depend on the context. Unlike full RL, only immediate reward matters and there is no long sequence of state
transitions.

Reinforcement Learning Full Notes Page 6

 Examples
- News recommendation: context is user profile, actions are articles, reward is click.

- Online advertisement: context is user and page information, action is ad, reward is conversion.

- Medical treatment selection: context is patient features, action is treatment, reward is outcome.

Point Multi-armed Bandit Contextual Bandit Full RL

State/context No context or fixed state Context observed before State evolves over time
action

Reward Immediate Immediate Immediate plus future

consequences

Transition No transition modelling No long transition sequence Transition from state to state

Difficulty Lowest Medium Highest

11. Returns and Value Functions

Return is the total reward the agent wants to maximize. In continuing tasks, future rewards are discounted using
gamma. Value functions estimate expected return and guide decision making.
G_t = R_{t+1} + gamma R_{t+2} + gamma^2 R_{t+3} + ...
V_pi(s) = E_pi[G_t | S_t=s]
Q_pi(s,a) = E_pi[G_t | S_t=s, A_t=a]

Why discount factor is used

- Makes infinite return finite when rewards continue forever.

- Models preference for immediate reward.

- Controls planning horizon.

- Helps mathematical convergence of Bellman updates.

12. Policy Search and REINFORCE - Basic Idea

Policy search methods directly search for a good policy instead of first learning a complete value function. The
policy is parameterized by theta, and the objective is to maximize expected return J(theta).
Objective: J(theta) = E_pi_theta[G_t]
Policy gradient idea: theta <- theta + alpha grad J(theta)

REINFORCE is a Monte Carlo policy gradient method. It updates policy parameters in the direction that increases
the log probability of actions that produced high return.
theta <- theta + alpha G_t grad log pi_theta(A_t | S_t)

REINFORCE key points

- It is model-free.

- It works with stochastic policies.

- It can handle continuous action spaces better than value-table methods.

- It has high variance because it uses complete returns.

- A baseline can be subtracted to reduce variance without changing expected gradient.

Reinforcement Learning Full Notes Page 7

 UNIT II - MDPs, Bellman Equations, Planning and Learning
1. Markov Decision Process - MDP
A Markov Decision Process is the mathematical model used in RL for sequential decision making. It assumes the
Markov property: the future depends only on the current state and action, not on the full past history.
MDP = (S, A, P, R, gamma)
S = set of states
A = set of actions
P(s'|s,a) = transition probability
R(s,a,s') = reward function
gamma = discount factor

Markov property
A state has the Markov property if it contains all information needed to predict the next state and reward after an
action. Formally, the next state depends only on present state and action.
P(S_{t+1} | S_t, A_t, S_{t-1}, A_{t-1}, ...) = P(S_{t+1} | S_t, A_t)

MDP modelling steps

- Identify the decision maker as agent.

- Define states with enough information for the Markov property.

- Define possible actions in each state.

- Define reward signal according to the goal.

- Define transition probabilities if model-based solution is used.

- Choose discount factor gamma.

- Select algorithm: DP, MC, TD, Q-learning, policy gradient, etc.

2. Bellman Expectation Equation

The Bellman expectation equation decomposes the value of a state into immediate reward plus discounted value of
the next state under a fixed policy pi. It is the foundation of policy evaluation.
V_pi(s) = sum_a pi(a|s) sum_{s',r} p(s',r|s,a)[r + gamma V_pi(s')]

For action-value function:

Q_pi(s,a) = sum_{s',r} p(s',r|s,a)[r + gamma sum_{a'} pi(a'|s')Q_pi(s',a')]

Explanation
- sum_a pi(a|s) averages over actions chosen by the policy.

- p(s',r|s,a) averages over possible next states and rewards.

- r is immediate reward.

- gamma V_pi(s') is discounted future return.

3. Bellman Optimality Equation

The Bellman optimality equation gives the value of the best possible policy. It chooses the action that gives
maximum expected return.
V*(s) = max_a sum_{s',r} p(s',r|s,a)[r + gamma V*(s')]

Q*(s,a) = sum_{s',r} p(s',r|s,a)[r + gamma max_{a'} Q*(s',a')]

Reinforcement Learning Full Notes Page 8

 Point Bellman Expectation Equation Bellman Optimality Equation

Policy For a fixed policy pi For the optimal policy

Operator Uses average over pi(a|s) Uses max over actions

Purpose Policy evaluation Finding optimal value/policy

Algorithms Iterative policy evaluation, MC, TD prediction Value iteration, Q-learning

4. Banach Fixed Point Theorem and Convergence Idea

Many RL algorithms are based on repeatedly applying Bellman operators. A fixed point is a value function that does
not change after applying the operator. The Banach fixed point theorem helps prove that repeated Bellman updates
converge under proper conditions.

Contraction mapping
An operator T is a contraction if it brings two value functions closer after application. With discount factor gamma <
1, Bellman operators are gamma-contractions under max norm.
||T V - T U|| <= gamma ||V - U||, where 0 <= gamma < 1

Banach fixed point theorem - exam statement

In a complete metric space, every contraction mapping has a unique fixed point, and repeated application of the
mapping from any starting point converges to that fixed point.

Use in RL
- Bellman expectation operator has unique fixed point V_pi.

- Bellman optimality operator has unique fixed point V*.

- Value iteration converges because Bellman optimality update is a contraction.

- Discount factor gamma controls speed of convergence.

Cauchy sequence idea

A sequence is Cauchy if its elements become arbitrarily close to each other as the sequence progresses. In value
iteration, repeated Bellman updates produce a sequence of value functions that becomes Cauchy and converges
to the fixed point.
For large m,n: ||V_m - V_n|| becomes very small.

5. Dynamic Programming in RL
Dynamic Programming (DP) solves MDPs when the complete model of the environment is known: transition
probabilities and rewards. DP uses Bellman equations to compute value functions and optimal policies.

Assumptions
- Finite state and action spaces.

- Known transition probabilities.

- Known reward function.

- Markov property holds.

DP methods
- Policy evaluation: compute V_pi for a fixed policy.

- Policy improvement: improve policy using the value function.

- Policy iteration: repeat evaluation and improvement.

Reinforcement Learning Full Notes Page 9

 - Value iteration: combine evaluation and improvement in one update.

6. Policy Evaluation
Policy evaluation computes the value function of a fixed policy. It repeatedly applies the Bellman expectation
update until values become stable.
V_{k+1}(s) = sum_a pi(a|s) sum_{s',r}p(s',r|s,a)[r + gamma V_k(s')]

Algorithm
- Initialize V(s) arbitrarily for all states.

- For each state, update V(s) using Bellman expectation equation.

- Repeat until maximum change in value is below a small threshold theta.

- Return V_pi.

7. Policy Improvement
After evaluating a policy, we can improve it by choosing actions greedily with respect to the current value function.
pi_new(s) = argmax_a sum_{s',r} p(s',r|s,a)[r + gamma V_pi(s')]

The policy improvement theorem states that if the new policy is greedy with respect to V_pi, then it is at least as
good as the old policy.

8. Policy Iteration
Policy iteration alternates between policy evaluation and policy improvement until the policy no longer changes.
Then it has reached an optimal policy.

Algorithm
- Initialize a random policy pi.

- Policy evaluation: compute V_pi.

- Policy improvement: make pi greedy with respect to V_pi.

- If policy is unchanged, stop; otherwise repeat.

Advantages
- Usually converges in few iterations.

- Gives both optimal value and optimal policy.

- Clear separation between evaluation and improvement.

Limitations
- Requires complete model of environment.

- Policy evaluation can be expensive for large state spaces.

- Not directly suitable for unknown environments.

9. Value Iteration
Value iteration directly applies Bellman optimality updates. It does not fully evaluate each policy. It repeatedly
updates each state using a max over actions.
V_{k+1}(s) = max_a sum_{s',r} p(s',r|s,a)[r + gamma V_k(s')]

Algorithm
- Initialize V(s) arbitrarily.

Reinforcement Learning Full Notes Page 10

 - For every state, update V(s) using Bellman optimality equation.

- Repeat until values converge.

- Extract policy by choosing greedy action in each state.

Point Value Iteration Policy Iteration

Main update Bellman optimality update Policy evaluation + policy improvement

Policy during process Implicit policy Explicit policy

Evaluation Partial/one-step Repeated until evaluated

Speed per iteration Cheaper iteration Costlier iteration

Number of iterations Can require many Usually fewer

Model required Yes Yes

10. Monte Carlo Methods

Monte Carlo (MC) methods learn from complete episodes. They do not require a model of the environment. They
estimate value functions by averaging actual returns observed after visiting states or state-action pairs.

MC prediction
- Generate episodes using policy pi.

- For each visited state, compute return G after that visit.

- Average returns for each state to estimate V_pi(s).

First-visit vs every-visit MC
Point First-Visit MC Every-Visit MC

Update condition Update only first time a state appears in an Update every time the state appears
episode

Complexity Less updates More updates

Convergence Converges under standard assumptions Also converges under standard

assumptions

MC control
MC control learns an optimal policy by estimating action values Q(s,a) and improving the policy greedily or
epsilon-greedily.

- On-policy MC control learns about the same policy that is used to generate behavior.

- Off-policy MC control learns about a target policy using data generated by a different behavior policy.

- Off-policy MC often uses importance sampling.

Importance sampling ratio: rho = product over time [ pi(A_t|S_t) / b(A_t|S_t) ]

11. Temporal Difference Learning - TD(0)

TD learning combines ideas of Monte Carlo and Dynamic Programming. Like MC, it learns from experience without
a model. Like DP, it bootstraps from current value estimates instead of waiting until episode end.
V(S_t) <- V(S_t) + alpha [ R_{t+1} + gamma V(S_{t+1}) - V(S_t) ]

The term in brackets is the TD error.

delta_t = R_{t+1} + gamma V(S_{t+1}) - V(S_t)

Reinforcement Learning Full Notes Page 11

 Point Monte Carlo TD(0)

Update time After complete episode After each step

Target Actual return G_t R + gamma V(S')

Bootstrapping No Yes

Works in continuing Difficult Yes

tasks

Bias/variance High variance, low bias Lower variance, some bias

12. TD Control: SARSA

SARSA is an on-policy TD control algorithm. Its name comes from the sequence State, Action, Reward, next State,
next Action. It updates Q-values using the action actually selected by the current policy.
Q(S_t,A_t) <- Q(S_t,A_t) + alpha [R_{t+1} + gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t)]

SARSA steps
- Initialize Q(s,a).

- Choose action A using epsilon-greedy policy.

- Take action A, observe reward R and next state S'.

- Choose next action A' using the same epsilon-greedy policy.

- Update Q using SARSA formula.

- Set S <- S', A <- A' and repeat.

13. Q-Learning
Q-learning is an off-policy TD control algorithm. It learns the optimal action-value function Q* while following an
exploratory behavior policy. The update uses the maximum Q-value at the next state.
Q(S_t,A_t) <- Q(S_t,A_t) + alpha [R_{t+1} + gamma max_a Q(S_{t+1},a) - Q(S_t,A_t)]

Q-learning steps
- Initialize Q(s,a) arbitrarily.

- Choose action using epsilon-greedy behavior policy.

- Take action, observe reward and next state.

- Update Q using max action value of next state.

- Repeat until convergence or enough training.

Point SARSA Q-Learning

Type On-policy Off-policy

Next action in update Uses actual A' selected by behavior policy Uses max_a Q(S',a)

Learning target Value of current behavior policy Optimal greedy policy

Risk behavior More conservative under exploration Can learn riskier optimal route

Formula target R + gamma Q(S',A') R + gamma max_a Q(S',a)

14. UCT - Upper Confidence Trees

Reinforcement Learning Full Notes Page 12

 UCT applies the UCB idea to tree search, especially Monte Carlo Tree Search. It balances exploring less-visited
branches and exploiting branches with high estimated value.
UCT score = average value + c sqrt( ln N(parent) / N(child) )

Use
- Game playing and planning.

- Large search spaces where full dynamic programming is impossible.

- Combines simulation/rollouts with exploration bonus.

Reinforcement Learning Full Notes Page 13

 UNIT III - Eligibility Traces, Function Approximation and Deep
RL
1. Eligibility Traces
Eligibility traces are a mechanism to assign credit to recently visited states or actions. They combine one-step TD
learning and Monte Carlo learning. The trace remembers how eligible each past state is for receiving the current
TD error.

Need of eligibility traces

- In TD(0), only the most recent state is updated.

- In MC, all states are updated after episode completion.

- Eligibility traces allow intermediate updates: recent states get more credit, older states get less credit.

- They often speed up learning.

Trace update
For state s:
e_t(s) = gamma lambda e_{t-1}(s) + 1, if s = S_t
e_t(s) = gamma lambda e_{t-1}(s), otherwise

Here lambda is trace decay parameter. lambda = 0 behaves like TD(0). lambda = 1 approaches Monte Carlo style
learning in episodic tasks.

2. Forward View and Backward View

Forward view
The forward view explains TD(lambda) using lambda-return. It looks forward into future rewards and combines
n-step returns using weights based on lambda.
G_t^lambda = (1-lambda) [G_t^(1) + lambda G_t^(2) + lambda^2 G_t^(3) + ...]

Backward view
The backward view is implementable online. It uses eligibility traces to update past states whenever a new TD error
is observed.
delta_t = R_{t+1} + gamma V(S_{t+1}) - V(S_t)
V(s) <- V(s) + alpha delta_t e_t(s)

Relation
The forward view is useful for theoretical understanding. The backward view is used in algorithms because it does
not need to wait for future rewards before updating.

3. TD(lambda)
TD(lambda) is a prediction algorithm that generalizes TD(0). It updates all eligible states using the TD error and
eligibility traces.

Algorithm
- Initialize V(s) and eligibility traces e(s)=0.

- At each step, observe S_t, R_{t+1}, S_{t+1}.

- Compute TD error delta_t.

- Increase trace for current state.

- Update all states according to alpha delta e(s).

Reinforcement Learning Full Notes Page 14

 - Decay all traces by gamma lambda.
V(s) <- V(s) + alpha delta_t e(s)

4. Eligibility Trace Control

Eligibility traces can be used with action-value methods. In control, traces are usually maintained for state-action
pairs instead of only states.

SARSA(lambda)
delta = R + gamma Q(S',A') - Q(S,A)
e(S,A) <- e(S,A) + 1
For all s,a: Q(s,a) <- Q(s,a) + alpha delta e(s,a)
e(s,a) <- gamma lambda e(s,a)

Watkins Q(lambda) idea

Q(lambda) extends Q-learning with traces. Because Q-learning is off-policy, traces may be cut or reset when a
non-greedy action is selected. This avoids learning wrong off-policy traces.

5. Function Approximation
Tabular RL stores a separate value for every state or state-action pair. This becomes impossible when state space
is very large or continuous. Function approximation represents value functions or policies using parameterized
functions.
Approximate value: V_hat(s,w) approx V(s)
Approximate action value: Q_hat(s,a,w) approx Q(s,a)

Why function approximation is needed

- Large state spaces cannot be stored in tables.

- Continuous states need generalization.

- Learning in one state should help similar states.

- Deep neural networks can learn useful representations from raw inputs.

Types
- Linear function approximation.

- State aggregation.

- Tile coding and radial basis functions.

- Decision trees and kernel methods.

- Neural networks and deep learning.

6. Linear Parameterization
In linear function approximation, each state is represented by a feature vector x(s), and the value is approximated
as a weighted sum of features.
V_hat(s,w) = w^T x(s)
Q_hat(s,a,w) = w^T x(s,a)

Gradient update
w <- w + alpha [target - V_hat(s,w)] grad V_hat(s,w)
For linear case: grad V_hat(s,w) = x(s)

Advantages
- Simple and computationally efficient.

Reinforcement Learning Full Notes Page 15

 - Easier convergence analysis than nonlinear networks.

- Generalizes across similar states using features.

Limitations
- Performance depends strongly on feature design.

- Cannot represent highly complex nonlinear value functions unless features are rich.

- May still diverge in some off-policy bootstrapping cases.

7. State Aggregation
State aggregation groups similar states together and gives them the same value estimate. It is one of the simplest
forms of function approximation.

Example
In a grid-world, instead of storing a value for every cell, nearby cells can be grouped into regions. All states in one
region share the same value.

Pros and cons

- Reduces memory and computation.

- Improves generalization.

- Can lose important distinctions between states.

- Bad grouping can reduce policy quality.

8. Function Approximation with Eligibility Traces

Eligibility traces can be extended to parameter vectors. Instead of storing traces for states, the algorithm stores
eligibility vector for weights.
e_t = gamma lambda e_{t-1} + grad V_hat(S_t,w)
w <- w + alpha delta_t e_t

For linear approximation:

e_t = gamma lambda e_{t-1} + x(S_t)

9. LSTD - Least Squares TD

Least Squares Temporal Difference learning uses a least-squares solution instead of small incremental gradient
updates. It is used mainly with linear function approximation.

Idea
LSTD tries to find weights w such that the approximate value function satisfies the projected Bellman equation. It
uses samples to build a system of linear equations.
A w = b
w = A^{-1} b

Advantages
- Often data efficient.

- Can converge faster than ordinary TD.

- Useful with linear features.

Limitations
- Matrix operations can be expensive for many features.

Reinforcement Learning Full Notes Page 16

 - Requires storing or updating matrix A.

- Mainly suitable for linear approximation.

10. LSTDQ and LSPI

LSTDQ
LSTDQ is an extension of LSTD for action-value functions Q(s,a). It estimates Q-values for a fixed policy using
linear function approximation.

LSPI - Least Squares Policy Iteration

LSPI combines LSTDQ with policy iteration. It evaluates the current policy using LSTDQ and then improves policy
greedily with respect to learned Q-values.

LSPI steps
- Collect sample transitions (s,a,r,s').

- Initialize a policy.

- Use LSTDQ to estimate Q for the current policy.

- Improve policy by choosing greedy actions according to Q.

- Repeat until policy becomes stable.

11. Fitted Q-Iteration

Fitted Q-Iteration is a batch RL method. It uses a dataset of transitions and a supervised learning regressor to
approximate Q-values.

Steps
- Collect dataset D = (s,a,r,s').

- Initialize Q approximation.

- Create target y = r + gamma max_{a'} Q(s',a').

- Train a regression model to predict y from (s,a).

- Repeat for multiple iterations.

Importance
Fitted Q-Iteration connects RL with supervised learning. DQN can be understood as a deep neural network version
of fitted Q-learning with additional stability techniques.

12. Deep Q-Network - DQN

DQN uses a neural network to approximate the Q-function. It became famous for learning Atari games from raw
pixels. DQN combines Q-learning with deep learning.
Loss = [ r + gamma max_{a'} Q_target(s',a') - Q(s,a;theta) ]^2

Main components
- Q-network: neural network that predicts Q-values for actions.

- Experience replay: stores transitions and samples random mini-batches for training.

- Target network: a separate network used to compute stable targets.

- Epsilon-greedy exploration: used to explore actions during training.

Why experience replay is used

Reinforcement Learning Full Notes Page 17

 - Breaks correlation between consecutive samples.

- Improves data efficiency by reusing past experience.

- Makes neural network training more stable.

Why target network is used

If the same network predicts both current Q and target Q, the target changes rapidly and training becomes
unstable. A target network changes slowly, giving more stable learning targets.

13. Policy Gradient Methods

Policy gradient methods directly optimize a parameterized policy. They are useful for continuous action spaces and
stochastic policies.
J(theta) = expected return under pi_theta
grad J(theta) = E[ grad log pi_theta(a|s) Q_pi(s,a) ]

Advantages
- Can handle continuous and high-dimensional action spaces.

- Learns stochastic policies naturally.

- Can optimize the policy directly without max over actions.

- Useful in robotics and control problems.

Limitations
- Usually sample inefficient.

- Gradient estimates can have high variance.

- Can converge to local optimum.

- Needs careful tuning of learning rate and reward scaling.

14. REINFORCE
REINFORCE is a Monte Carlo policy gradient algorithm. It waits until return is known and then updates policy
parameters.
theta <- theta + alpha G_t grad log pi_theta(A_t|S_t)

With baseline
theta <- theta + alpha [G_t - b(S_t)] grad log pi_theta(A_t|S_t)

The baseline reduces variance. A common baseline is V(s). It does not change the expected gradient because it
does not depend on the selected action.

15. Actor-Critic Methods

Actor-critic methods combine policy gradient and value function learning. The actor represents the policy. The critic
estimates the value function and tells the actor how good an action was.

Components
- Actor: updates policy parameters theta.

- Critic: updates value parameters w.

- TD error: used as advantage signal for policy update.

delta = R + gamma V(S',w) - V(S,w)
Critic: w <- w + alpha_w delta grad V(S,w)
Actor: theta <- theta + alpha_theta delta grad log pi_theta(A|S)

Reinforcement Learning Full Notes Page 18

 Advantages over REINFORCE
- Can update online after each step.

- Lower variance due to critic.

- Works well in continuing tasks.

- Forms basis of many modern deep RL algorithms.

Reinforcement Learning Full Notes Page 19

 UNIT IV - Hierarchical RL, Options and POMDP
1. Hierarchical Reinforcement Learning - HRL
Hierarchical Reinforcement Learning decomposes a complex task into smaller subtasks. Instead of learning only
primitive actions, the agent can learn and use temporally extended actions such as skills, options, or subroutines.

Need of HRL
- Large tasks are difficult to learn using only primitive actions.

- Subtasks can be reused in different problems.

- Learning becomes faster due to abstraction.

- Long-horizon planning becomes easier.

- Human-like tasks naturally have hierarchy.

Example
A delivery robot may have high-level actions: go to room, pick object, deliver object. Each high-level action
internally uses many primitive movements.

2. Types of Optimality in HRL

When hierarchy restricts policies, different definitions of optimality arise.

Type Meaning

Flat optimality Best possible policy without hierarchical restrictions. It is the global optimum over all
primitive-action policies.

Hierarchical optimality Best policy among all policies that follow the given hierarchy. It may be worse than flat
optimality if hierarchy restricts choices.

Recursive optimality Each subtask policy is optimal assuming its child subtasks are fixed. It is easier to learn
but may not give the best hierarchical policy.

3. Semi-Markov Decision Process - SMDP

An SMDP generalizes MDPs by allowing actions to take variable amounts of time. This is important for options and
skills because a high-level action may run for several time steps before terminating.

MDP vs SMDP
Point MDP SMDP

Action duration One time step Variable number of time steps

Action type Primitive action Primitive or temporally extended action

Reward One-step reward Cumulative reward during action duration

Use Standard RL Options and hierarchical RL

4. Options Framework
An option is a temporally extended action. It has its own policy and termination condition. Options allow the agent to
make decisions at a higher level of abstraction.
Option o = (I_o, pi_o, beta_o)
I_o = initiation set: states where option can start
pi_o = internal policy of the option

Reinforcement Learning Full Notes Page 20

 beta_o(s) = probability that option terminates in state s

Example
In a building navigation task, an option could be Go to elevator. It can start in hallway states, follows an internal
navigation policy, and terminates when the elevator is reached.

Advantages
- Reduces decision frequency.

- Improves exploration using meaningful skills.

- Allows transfer of learned skills.

- Makes planning and learning more scalable.

5. Learning with Options

Learning with options means learning which option to choose at high level and sometimes also learning the internal
policy of each option.

SMDP Q-learning with options

Q(s,o) <- Q(s,o) + alpha [ r + gamma^k max_{o'}Q(s',o') - Q(s,o) ]

Here k is the duration of the option, and r is the cumulative discounted reward received while executing the option.

Intra-option learning
Intra-option learning updates option values during execution of an option, rather than waiting until the option
terminates. This can make learning more efficient.

6. Hierarchical Abstract Machines - HAM

A Hierarchical Abstract Machine represents a hierarchy of partial programs that restrict the agent choices. The
machine contains states where some actions are forced, some are choices, and some call submachines.

HAM components
- Action states: execute a primitive action.

- Choice states: agent chooses among allowed transitions.

- Call states: call another abstract machine/subroutine.

- Stop states: return control to previous machine.

Key idea
HAM does not directly specify a policy. Instead, it restricts the space of possible policies. RL is then used to learn
the best policy within these restrictions.

7. MAXQ Decomposition
MAXQ is a hierarchical RL method that decomposes the value function of a task into values of subtasks. It
represents a task hierarchy and learns value functions for subtasks.

MAXQ value decomposition

The value of executing a subtask can be decomposed into two parts: reward for completing the subtask itself and
expected value after the subtask terminates.
Q(parent, child, s) = V(child, s) + C(parent, child, s)
V(child,s) = value of completing child task
C(parent,child,s) = completion function: expected future reward after child ends

Reinforcement Learning Full Notes Page 21

 Advantages
- Provides structured decomposition of large tasks.

- Subtask values can be reused.

- Improves interpretability.

- Can reduce complexity when hierarchy is well designed.

Limitations
- Requires good task hierarchy.

- May give hierarchical optimality rather than flat optimality.

- Designing subtasks can be difficult.

8. Option Discovery
Option discovery is the problem of automatically finding useful options or skills. Manually designing options is not
always possible, so algorithms try to discover subgoals or repeated behavior patterns.

Common approaches
- Bottleneck states: states that are frequently crossed while moving between regions, such as doorways.

- Graph/community methods: find important states in state-transition graph.

- Diversity-based skills: learn skills that produce different outcomes.

- Successor features: identify subgoals based on long-term state occupancy.

- Expert demonstrations: extract repeated subroutines from expert trajectories.

9. POMDP - Partially Observable Markov Decision Process

A POMDP is used when the agent cannot directly observe the true state of the environment. Instead, it receives
observations that provide partial information about the hidden state.
POMDP = (S, A, P, R, O, Z, gamma)
S = hidden states
A = actions
P = transition model
R = reward function
O = observations
Z(o|s,a) = observation probability
gamma = discount factor

Why POMDP is needed

- Sensors may be noisy.

- Agent may not see the complete environment.

- Same observation may correspond to different actual states.

- Memory or belief state is needed for good decisions.

Examples
- Robot localization with noisy sensors.

- Medical diagnosis where true disease state is hidden.

- Card games where opponent cards are hidden.

- Navigation in fog or dark environment.

Reinforcement Learning Full Notes Page 22

 10. Belief State
A belief state is a probability distribution over possible hidden states. It summarizes the agent uncertainty about the
true state. A POMDP can be converted into a belief-state MDP, but the belief space is continuous.
b(s) = probability that current hidden state is s

Belief update idea

After taking an action and receiving an observation, the agent updates its belief using transition probabilities and
observation probabilities.
b'(s') proportional to Z(o|s',a) sum_s P(s'|s,a)b(s)

11. Solving POMDPs

Solving POMDPs exactly is difficult because the agent must reason over beliefs, not directly visible states.
Approximate methods are commonly used.

Methods
- Exact value iteration: possible only for small POMDPs.

- Point-based value iteration: updates values for selected belief points.

- Policy search: directly optimize a policy that uses history or belief.

- QMDP approximation: assumes uncertainty will disappear after one action.

- Recurrent neural policies: use memory to handle partial observability.

- Monte Carlo planning: sample possible hidden states and observations.

POMDP limitations
- Belief space is continuous and high-dimensional.

- Exact solution is computationally expensive.

- Requires observation and transition models.

- Approximation quality depends on selected method.

Reinforcement Learning Full Notes Page 23

 Exam-Oriented Difference Tables
Model-Based vs Model-Free RL
Point Model-Based RL Model-Free RL

Environment model Learns or uses P and R Does not require P and R

Planning Can plan using model Learns directly from experience

Examples Dynamic programming, planning with MC, TD, SARSA, Q-learning, DQN
learned model

Sample efficiency Usually more sample efficient May require more data

Computation Planning can be expensive Usually simpler per step

Risk Wrong model can mislead planning Less model bias but more trial-and-error

On-Policy vs Off-Policy
Point On-Policy Off-Policy

Meaning Learns value of the same policy used to act Learns target policy different from behavior
policy

Exploration effect Exploration affects learned policy value Can learn greedy/optimal target while
exploring

Examples SARSA, on-policy MC Q-learning, off-policy MC

Stability Often more stable Can be less stable with function

approximation

Use When behavior and target policy are same When learning from another policy/data

DP vs MC vs TD
Point Dynamic Programming Monte Carlo Temporal Difference

Model needed Yes No No

Update target Expected Bellman backup Actual return Bootstrapped TD target

When update happens Sweeps over states After episode ends After each step

Bootstrapping Yes No Yes

Works for continuing Yes Not directly Yes

tasks

Examples VI, PI First-visit MC TD(0), SARSA, Q-learning

REINFORCE vs Actor-Critic
Point REINFORCE Actor-Critic

Type Monte Carlo policy gradient TD based policy gradient

Update time After complete return Step-by-step possible

Variance High Lower due to critic

Bias Low bias Some bias due to bootstrapping

Reinforcement Learning Full Notes Page 24

 Point REINFORCE Actor-Critic

Value function Optional baseline Critic is essential

Sample efficiency Lower Better

Algorithms - Quick Writing Format

Value Iteration - 14 Mark Answer Skeleton
- Define value iteration as DP algorithm for solving known MDPs.

- Write Bellman optimality update.

- Explain initialization and iterative updates.

- Explain convergence using contraction mapping.

- Show policy extraction by greedy action selection.

- Mention advantages and limitations.

Repeat until convergence:
V(s) <- max_a sum_{s',r}p(s',r|s,a)[r + gamma V(s')]
Policy: pi(s) = argmax_a sum_{s',r}p(s',r|s,a)[r + gamma V(s')]

Policy Iteration - 14 Mark Answer Skeleton

- Define policy iteration.

- Explain policy evaluation.

- Explain policy improvement.

- Repeat until policy stable.

- Give comparison with value iteration.

- Mention model requirement and cost.

Q-Learning - 14 Mark Answer Skeleton

- Define Q-learning as off-policy TD control.

- Write Q-learning update formula.

- Explain terms: alpha, gamma, reward, max next Q.

- Write step-wise algorithm.

- Explain exploration using epsilon-greedy.

- Compare with SARSA.

- Mention advantages and limitations.

DQN - 14 Mark Answer Skeleton

- Start with limitation of tabular Q-learning in large state spaces.

- Define DQN as Q-learning with neural network approximation.

- Write target and loss function.

- Explain experience replay and target network.

- Explain epsilon-greedy exploration.

- Mention applications, advantages and limitations.

Reinforcement Learning Full Notes Page 25

 POMDP - 14 Mark Answer Skeleton
- Define partial observability.

- Write POMDP tuple.

- Explain hidden states, observations and observation model.

- Explain belief state and belief update.

- Give examples.

- Explain solving methods and limitations.

Most Expected Questions

- Explain RL framework with agent-environment interaction and applications.

- Explain exploration vs exploitation and multi-armed bandit problem.

- Explain UCB and UCB1 theorem idea.

- Explain Thompson sampling and median elimination.

- Define MDP and explain Bellman expectation and optimality equations.

- Explain Banach fixed point theorem and its role in value iteration convergence.

- Compare value iteration and policy iteration.

- Explain Monte Carlo methods and TD(0).

- Explain SARSA and Q-learning with difference.

- Explain eligibility traces and TD(lambda).

- Explain function approximation, linear parameterization and state aggregation.

- Explain LSTD, LSTDQ, LSPI and fitted Q-iteration.

- Explain DQN with experience replay and target network.

- Explain policy gradient, REINFORCE and actor-critic.

- Explain HRL, SMDP, options and MAXQ.

- Explain POMDP and belief-state solution idea.

Last-Day Revision Checklist

- Revise all formulas: return, V, Q, Bellman equations, TD, SARSA, Q-learning, REINFORCE.

- Practise difference tables: DP vs MC vs TD, VI vs PI, SARSA vs Q-learning, on-policy vs off-policy.

- Write algorithm steps from memory for VI, PI, MC, TD(0), SARSA, Q-learning, DQN.

- Prepare one example each for bandit, MDP, POMDP and HRL.

- Revise convergence terms: contraction, fixed point, Cauchy sequence, Banach theorem.

- For theory answers, include definition, diagram/framework, formula, explanation, advantages, limitations.

Mini Glossary
Term One-line revision

Return Discounted sum of future rewards.

Reinforcement Learning Full Notes Page 26

 Term One-line revision

Policy Rule for selecting actions in states.

Value function Expected return from a state or action.

Bellman equation Recursive equation relating current value to immediate reward and next value.

Bootstrapping Updating an estimate using another estimate.

Contraction Mapping that brings value functions closer.

Eligibility trace Temporary memory of recently visited states/actions.

Function approximation Using parameters/features/neural networks to represent values or policies.

Option Temporally extended action with initiation set, policy and termination condition.

Belief state Probability distribution over hidden states in POMDP.

End note: For scoring answers, do not write only definitions. Add formulas, algorithm steps, differences and
limitations. RL papers use heavy mathematics, but exam answers usually reward clear structure and correct equations.

Reinforcement Learning Full Notes Page 27