6 posts tagged with "rl"

Known MDP vs Unknown MDP​

Aspect	Known MDP	Unknown MDP
Environment Knowledge ($P, R$)	Full knowledge of state transition dynamics $P$ and reward function $R$	$P$ and $R$ are unknown; agent must explore the environment
Problem Approach	Well-defined optimization problem $\rightarrow$ Pure planning via computation	Trial-and-error interaction $\rightarrow$ Must learn and optimize simultaneously
Primary Goal	Directly compute the optimal policy ($\pi_*$)	Learn and optimize policies without prior model knowledge
Representative Methods	Value Iteration, Policy Iteration (Dynamic Programming)	Monte Carlo, Q-Learning, SARSA (Reinforcement Learning)
Paradigm	Model-based (Planning)	Model-free (Reinforcement Learning)

Model-based vs Model-free​

Aspect	Model-Based Learning	Model-Free Learning
Model Access ($P, R$)	Has full access to transition dynamics $P$ and reward function $R$	No access to environment dynamics ($P$ and $R$ are unknown)
Optimization Approach	Direct mathematical computation and planning using the known model	Direct learning and trial-and-error optimization through interaction
Estimation Source	Computes values and optimal policy $\pi_*$ via dynamic programming equations	Estimates $v_\pi, q_\pi$, and $\pi_*$ directly from sampled experience
Computation vs. Sampling	Pure computation / Planning (requires no real-time environment sampling)	Sample-based learning (requires trajectories / episodic experience)
Typical Methods	Policy Iteration, Value Iteration (DP)	Monte Carlo Methods, TD Learning, Q-Learning, SARSA

Monte Carlo Methods​

• A Computational technique that uses random sampling and statistical methods to solve complex problems and estimate numerical results.
  • Named after the Monte Carlo Casino in Monaco.
  • It means Estimate an unknown quantity by sampling, and averaging what you observe.
• Used fo any estimation method whose operation involves a significant random component.
• Used in mathematics, physics, engineering, finance, computer science, etc.
• It is particularly valuable when an analytical solution is difficult or impossible to obtain.

Estimating $\pi$ by Sampling (Monte Carlo Simulation)​

• Mechanism:
  • Generate uniform random points $(x, y) \in [-1, 1] \times [-1, 1]$.
  • Count points falling inside the unit circle ($x^2 + y^2 \le 1$).
  • Estimate $\pi$ via area proportions:

$$\begin{aligned} \frac{\text{Area}_{circle}}{\text{Area}_{square}} = \frac{\pi}{4} \\ & \pi \approx 4 \times \frac{\text{\#points inside circle}}{\text{\#total points}} \end{aligned}$$

• Empirical Validation:
  • Total samples ($n$): $3000$ points
  • Estimated value: $\pi = 3.1386666666666665$
  • Relative error: $-0.0931\%$ from true value ($\approx 3.14159265$)

Monte Carlo Prediction​

$v_\pi(s) = \mathbb{E}_{\pi}[G_t | S_t = s] \approx \frac{1}{N} \sum_{i=1}^{N(s)} G^{(i)}$

• $\frac{1}{N} \sum_{i=1}^{N(s)} G^{(i)}$: Mean of the returns/rewards
• Model-Free Learning: Operates without prior knowledge of transition dynamics $P$ or reward function $R$.
• Learning from Complete Episodes: Learns state-value functions $v_\pi$ exclusively from full trajectories under policy $\pi$. Only works for episodic tasks where termination at step $T$ is guaranteed.
• No Bootstrapping: Does not update estimates using other value estimates $v(s')$; instead, updates rely solely on actual empirical returns observed at the end of the episode.
• Empirical Mean Returns: The value of state $s$ is estimated by the sample average of all observed returns starting from $s$:

An Episode of Experience & Return Formulation​

• Trajectory Structure: $S_0 \xrightarrow{A_0, R_1} S_1 \xrightarrow{A_1, R_2} S_2 \dots \xrightarrow{A_{T-1}, R_T} S_T$
• Discounted Return ($G_t$): $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots + \gamma^{T-t-1} R_T$
• Discount Factor ($\gamma = 1$): For episodic tasks with terminal-only rewards (such as Blackjack), setting $\gamma = 1$ is standard practice because the episode length is finite.

First-Visit Monte Carlo​

• First-Visit MC estimates the value function $V(s)$ by averaging returns following only the first occurrence of state $s$ within each sampled episode.
• Algorithmic Flow:
  • Initialize counters $N(s) \leftarrow 0$ and accumulate returns: $G(s) \leftarrow 0 \quad \forall s \in S$
  • Sample a complete episode $i = \{S_{i,0}, A_{i,1}, R_{i,2}, \dots, S_{i,T_i}\}$ generated under policy $\pi$
  • Compute return $G_{i,t} = \sum_{k=t+1}^{T_i} \gamma^{k-t-1} R_{i,k}$ from step $t$ to termination.
  • Only for the first time step $t$ where state $s$ appears in episode $i$:
    • $N(s) \leftarrow N(s) + 1$ (Increment counter for total first visits)
    • $G(s) \leftarrow G(s) + G_{i,t}$ (Increment total return)
    • $V(s) \leftarrow \frac{G(s)}{N(s)}$ (Update the value by mean return)

$A \xrightarrow{R_1=1} B \xrightarrow{R_2=2} A \xrightarrow{R_3 = 1} C \xrightarrow{R_4 = 1} \text{terminal}$

State s	$N(s)$	$G(s)$	$V(s) = \frac{G(s)}{N(s)}$
A	1	9	9.00
B	1	8	8.00
C	1	5	5.00

Every-Visit Monte Carlo​

• Every-Visit MC treats every single occurrence of state $s$ within an episode as a valid data sample, accumulating its corresponding return into the empirical mean.
• Algorithmic Flow:
  • Initialize counters $N(s) \leftarrow 0$ and accumulate returns: $G(s) \leftarrow 0 \quad \forall s \in S$
  • Sample a complete episode $i = \{S_{i,0}, A_{i,1}, R_{i,2}, \dots, S_{i,T_i}\}$ generated under policy $\pi$
  • Compute return $G_{i,t} = \sum_{k=t+1}^{T_i} \gamma^{k-t-1} R_{i,k}$ from step $t$ to termination.
  • For each time step $t$ where state $s$ appears in episode $i$:
    • $N(s) \leftarrow N(s) + 1$ (Increment counter for total visits)
    • $G(s) \leftarrow G(s) + G_{i,t}$ (Increment total return)
    • $V(s) \leftarrow \frac{G(s)}{N(s)}$ (Update the value by mean return)

$A \xrightarrow{R_1=1} B \xrightarrow{R_2=2} A \xrightarrow{R_3 = 1} C \xrightarrow{R_4 = 1} \text{terminal}$

State s	$N(s)$	$G(s)$	$V(s) = \frac{G(s)}{N(s)}$
A	2	9+6=15	7.50
B	1	8	8.00
C	1	5	5.00

Dimension	First-Visit MC	Every-Visit MC
Returns used per episode	Only the first occurrence	Every occurrence
Sample independence	Independent across episodes (i.i.d.)	Correlated within an episode (mitigated by sampling)
Bias (finite samples)	Unbiased	Biased, but $\text{bias} \to 0$
Convergence	Consistent (Law of Large Numbers)	Consistent (as $\text{episodes} \to \infty$)
Implementation	Requires a "seen this episode?" check	Simpler — no check needed
Practical Use	Standard theoretical baseline	Frequently preferred (uses all available data)

Incremental Mean​

$\mu_k = \frac{1}{k} \sum_{j=1}^{k} x_j$

$$\begin{aligned} \mu_{k+1} &= \frac{1}{k+1} \sum_{j=1}^{k+1} x_j \\ &= \frac{1}{k+1} \left( \sum_{j=1}^{k} x_j + x_{k+1} \right) \\ &= \frac{1}{k+1} \left( k \mu_k + x_{k+1} \right) \\ &= \mu_k + \frac{1}{k+1} (x_{k+1} - \mu_k) \end{aligned}$$

• New estimate = Old estimate + step-size * (new sample - old estimate).
• Memory efficient: Only need to store the old estimate ($\mu_k$) and the number of visits ($k$).

Incremental Monte Carlo​

• Updates the value function $V(s)$ incrementally after each trajectory without requiring memory to store individual past returns.
• Algorithmic Flow:
  • Initialize $N(s) \leftarrow 0$ and $V(s) \leftarrow 0$ for all $s \in S$.
  • Episode sampling: Execute episode $i$ under policy $\pi$ and compute returns $G_{i,t} = \sum_{k=t+1}^{T_i} \gamma^{k-t-1} R_{k}$.
  • Incremental update: For each visited state $s$ at time step $t$:
    • $N(s) \leftarrow N(s) + 1$ (Increment counter for total visits)
    • $V(s) \leftarrow V(s) + \alpha (G_{i,t} - V(s))$ (Update the value by mean return)
    • Where $G_{i,t} - V(s)$ represents the temporal difference (TD) error between the sampled return target and the current estimate.
• Choice step size $\alpha$
  • $\alpha = \frac{1}{N(s)}$: Replicates the exact empirical sample-average of Every-Visit MC where all observed samples receive equal weight.
  • $\alpha = \text{constant}$: Implements an exponential recency-weighted running average that decays outdated experience, making it suited for non-stationary environments where MDP dynamics change over time.
• Cons:
  • Requires a significant number of episodes to converge to the true value function.
  • Requires to terminate the episode.

Model-free Control​

• The MDP model is unknown, or too large/complex to use directly.
• But experience can be sampled.
• Applications:
  • Robo soccer
  • Autonomous vehicles
  • Robotics
  • Game playing
  • Recommender systems
  • Finance & portfolio management

On-Policy vs Off-Policy​

Dimension	On-Policy Learning	Off-Policy Learning
Definition	Evaluates and improves the exact same policy currently used to generate action decisions	Evaluates/improves a target policy ($\pi$) while behaving via a different behavior policy ($b$)
Data Generation	Trajectories must be generated by the current active policy $\pi$	Trajectories can come from exploratory policies, historical logs, or human demonstrations
Exploration Trade-off	Must balance exploration directly within the target policy (e.g., $\epsilon$-greedy)	Separates exploration (behavior policy) from exploitation/optimality (target policy)
Representative Algorithms	GLIE Monte Carlo Control, SARSA	Q-Learning, Deep Q-Networks (DQN)

General Policy Iteration​

• Alternates between Policy Evaluation ($V \approx v_\pi$ or $Q \approx q_\pi$) and Policy Improvement ($\pi \leftarrow \text{greedy}$).
• This interplay drives the system asymptotically toward the optimal pair $(v_*, \pi_*)$ or $(q_*, \pi_*)$.

$\pi'(s) = \text{argmax}_{a \in A} \big( \mathcal{R}(s, a) + \gamma \sum_{s' \in S} \mathcal{P}(s' | s, a) V(s') \big)$

• Why $V(s)$ Fails in Model-Free Settings:
  • Finding the maximizing action over $V(s)$ strictly requires the transition model $P(s' \mid s, a)$ and reward function $R(s, a)$.
  • In Model-Free RL, these dynamics are unavailable; hence, $V(s)$ alone cannot guide policy updates without an explicit environment model.

$\pi'(s) = \text{argmax}_{a \in A}Q(s,a)$

• Model-Free Advantage:
  • By estimating $Q(s, a)$ directly through sample episodes, policy improvement requires no knowledge of $P$ or $R$.
  • This fundamental shift makes $Q(s, a)$ estimation the standard paradigm for Model-Free Control (Monte Carlo Control, SARSA, Q-Learning).

	$V(s)$	$Q(s, a)$
Question	How good is this state?	How good is this action in this state?
Includes Action?	No	Yes
Policy Evaluation	Very suitable	Slightly more difficult
Policy Improvement	Requires a model	Directly possible
Model-Free Control	Inconvenient	Very suitable

• This is why MC Control estimates $q_\pi(s,a)$, not $v_\pi(s)$.

Exploration Problem​

$$a = \arg\max_a Q(s,a)$$

• A greedy agent always chooses the action with the highest current estimated value.
• But what if the current $Q(s,a)$ estimates are inaccurate?

Mystery Box Example​

Initially,

$$Q(\text{red}) = 0, \qquad Q(\text{blue}) = 0$$

1. Open the red box:
   $R = 0 \rightarrow Q(\text{red}) = 0$

2. Open the blue box:
   $R = +1 \rightarrow Q(\text{blue}) = 1$

3. Keep opening the blue box:
   $R = +1, +3, +2, \ldots \rightarrow Q(\text{blue}) \approx 2$

4. A purely greedy agent now keeps choosing the blue box because
   $Q(\text{blue}) > Q(\text{red})$.

5. However, the red box may actually be better. For example,
   $\mathbb{E}[R \mid \text{red}] = 5$.

   The agent does not know this because it sampled the red box only once.

Exploitation vs. Exploration​

• Exploitation: Choose the action that currently has the highest estimated value.
• Exploration: Try less-sampled or unfamiliar actions to discover whether they may actually be better.
• In this example, the agent should occasionally explore the red box because it has not been sampled enough to confidently conclude that it is worse.

$\epsilon$-Greedy Exploration​

$$\pi(a|s) = \begin{cases} \text{greedy action \quad with high probability} \\ \text{random action \quad with probability $\epsilon$} \\ \end{cases}$$

• if $\epsilon = 0.1$, then the agent will choose the greedy action with probability $0.9$ (Exploitation)
• And the random action with probability $0.1$ (Exploration).
• Policy Improvement Theorem:
  • for any $\epsilon$-greedy policy $\pi$
  • The $\epsilon$-greedy policy $\pi'$ is as good or better than the original policy $\pi$: $v_{\pi'}(s) \geq v_{\pi}(s)$

Monte Carlo Control​

• Traditional Policy Iteration:
  • Fix the policy $\pi$.
  • Evaluate the current policy until $Q$ is sufficiently close to $q_\pi(s,a)$.
  • Improve the policy using the estimated action values.
  • Repeat policy evaluation and policy improvement.
• Monte Carlo Control:
  • Perform MC Policy Evaluation after every episode.
  • Improve the policy using $\epsilon$-greedy after every episode.
  • $Q_1 \rightarrow \pi_1 = \epsilon\text{-greedy}(Q_1)$
  • $Q_2 \rightarrow \pi_2 = \epsilon\text{-greedy}(Q_2)$
  • $\cdots$
  • Eventually approaches $(q_*, \pi_*)$ under appropriate convergence conditions.

$$\text{Evaluate a little} \rightarrow \text{Improve} \rightarrow \text{Evaluate a little} \rightarrow \text{Improve} \rightarrow \cdots$$

GLIE​

Greedy in the Limit with Infinite Exploration

1. $\lim_{k \to \infty} N_k(s,a) = \infty$
2. $\lim_{k \to \infty} \pi_k(a|s) = 1(a = \argmax_{a' \in A} Q_k(s,a'))$

• Explore enough early -> Explore less over time -> Eventually greedy.
  • $N_k(s,a)$: How many times the state-action pair $(s,a)$ has been visited in the $k$-th episode.
  • $\pi_k \rightarrow \text{greedy}(Q_k)$
• Infinite exploration first, greedy behavior in the limit.

GILE Monte Carlo Control​

• Algorithm flow:
  • Run episode $k = \{S_0, A_0, R_1, \dots, S_{T}\}$ with policy $\pi_k$.
  • For each state-action pair $(s,a)$ in the episode:
    • $N_k(s,a) \leftarrow N_k(s,a) + 1$
    • $Q_k(s,a) \leftarrow Q_k(s,a) + \frac{1}{N_k(s,a)} (G_k - Q_k(s,a))$
  • Improve the policy based on the new $Q$ value.
    • $\epsilon \leftarrow \frac{1}{k}$
    • $\pi \leftarrow \epsilon\text{-greedy}(Q)$
  • Repeat until convergence.
• old estimate + step-size * (new sample - old estimate).
  • old estimate = $Q(S_t, A_t)$
  • new sample = $G_t$
  • step-size = $\frac{1}{N_k(s,a)}$
• Run Episode → Update Q → Reduce $\epsilon$ → Improve Policy

DP vs MC​

• Dynamic Programming:
  • Model-based
  • Bootstrapping: Updating a value estimate using another estimated value instead of waiting for the final outcome.
  • Lower variance
• Monte Carlo:
  • Model-free
  • No bootstrapping
  • Uses complete sampled returns
  • Requires episodic tasks
  • Higher variance

MDP​

$(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma)$

• At each time step $t$, the agent observes state $S_t \in \mathcal{S}$ and chooses action $A_t \in \mathcal{A}$
• Receives reward $R_{t+1} \in \mathcal{R}$
• Transitions to a new state $S_{t+1}$

Transition Dynamics​

Transition Probability

• How the environment responds to an action, independent of the agent's policy
• Policy: Whether to brake or accelerate when the traffic light is yellow.
• Transition Dynamics: How much the car decelerates after braking, and what the resulting next state is.

$P(s'|s,a) = P(S_{t+1} = s'|S_t = s, A_t = a)$

Policy​

• A policy is the agent’s rule for choosing actions.
• It tells the agent what action to take in a given state.
• It defines agent's behavior.

$\text{Deterministic Policy}: \pi(s) = a$

• Direct mapping, and no randomness
• All probability on one action

$\text{Stochastic Policy}: \pi(a|s) = P(A_t = a | S_t = s)$

• A probability distribution over actions.
• More general, all four Bellman Equations are stochastic, use $\pi(a|s)$ to represent the policy.
• Policy is what the agent controls.

Value Functions​

$v_\pi(s) = \mathbb{E}_\pi[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s]$

• How good is this state?
• $\mathbb{E}_\pi[G_t | S_t = s]$

$q_\pi(s,a) = \mathbb{E}_\pi[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s, A_t = a]$

• How good is this action in this state?
• $\mathbb{E}_\pi[G_t | S_t = s, A_t = a]$

$v_\pi(s) = \sum_{a \in \mathcal{A}} \pi(a|s) q_\pi(s,a)$

• The average value of the actions, weighted by the probability of choosing each action.
  • $a_1$ is brake
  • $a_2$ is accelerate
  • $v_\pi(s) = 0.8 * 10 + 0.2 * 20 = 10$

$$q_\pi(s,a) = \mathcal{R}(s,a) + \gamma \sum_{s' \in \mathcal{S}} P(s'|s,a) v_\pi(s')$$

• The value of taking action $a$ in state $s$: the immediate reward plus the discounted expected value of the possible next states.

Four Types of Bellman Equations​

$$\begin{aligned} &v_\pi(s) = \sum_{a} \pi(a|s) q_\pi(s,a) \\ &q_\pi(s,a) = \mathcal{R}(s,a) + \gamma \sum_{s'} P(s'|s,a) v_\pi(s') \\ &v_\pi(s) = \sum_{a} \pi(a|s) \left[ \mathcal{R}(s,a) + \gamma \sum_{s'} P(s'|s,a) v_\pi(s') \right] \\ &q_\pi(s,a) = \mathcal{R}(s,a) + \gamma \sum_{s'} P(s'|s,a) \sum_{a'} \pi(a'|s') q_\pi(s',a') \end{aligned}$$

• Evaluate a state: $v_\pi(s)$
• Evaluate an action: $q_\pi(s,a)$
• Calculate Bellman by only $v$: Third equation
• Calculate Bellman by only $q$: Fourth equation

Dynamic Programming​

Optimization method for sequential problem

• Dynamic: Sequential or Temporal component
• Programming: Optimizing a program or policy

• Sub Problem
• Optimal Solution

Prediction and Control​

• Prediction: Evaluate a given policy $v_\pi(s)$
• Control: Find the optimal policy $\pi_*$

Policy Improvement​

• $\pi \to v_\pi \to \pi'$
• $\pi' = \text{greedy}(v_\pi)$
• Evaluate current policy, Improve it greedily, then get a better policy

Modified Policy Iteration​

• Policy iteration can be computationally expensive
• MPI: cut off the policy evaluation after a few iterations $k$ then step to policy improvement.
  • $k = 1 \Rightarrow \text{Value iteration}$
  • $k = 3,4 \Rightarrow \text{Modified Policy iteration}$
  • $k \quad \text{is large enough} \Rightarrow \text{Policy iteration}$

Poisson Distribution Formulation​

$P(X = n) = \frac{\lambda^n e^{-\lambda}}{n!}$

• How many times an event occurs within a fixed interval of time (or space) when we only know the long-term average rate ($\lambda$).
• $n$: The actual number of requests or returns ($n \in \{0, 1, 2, \ldots\}$)
• $\lambda$: The expected/average number of requests or returns
• $e$: Euler's number (2.71828)
• $n!$: Factorial of $n$

Deterministic Value Iteration​

$v_*(s) = \max_{a} \left( \mathcal{R}(s,a) + \gamma \sum_{s'} P(s'|s,a) v_*(s') \right)$

• If solutions to sub-problems $v_*(s')$ are known, the optimal value $v_*(s)$ for the current state can be computed directly.
• Value signals propagate backwards across the state space from states with terminal rewards.

Value Iteration​

$v_{k+1}(s) = \max_{a} \left( \mathcal{R}(s,a) + \gamma \sum_{s'} P(s'|s,a) v_k(s') \right)$

• Infinite ($\infty$) iterations are required to converge exactly to $v_*$.
• In practical implementations, iteration terminates when the maximum value change between iterations is less than a small threshold $\theta$.

Dynamic Programming ALgorithms​

Problem	Bellman Equation	Algorithm
Prediction	Bellman Expectation: $v_{k+1}(s) = \sum_{a \in A} \pi(a \mid s) \left( R(s, a) + \gamma \sum_{s' \in S} P(s' \mid s, a) v_k(s') \right)$	Iterative Policy Evaluation
Control	Bellman Expectation + Greedy Policy Improvement: $v_{k+1}(s) = \sum_{a \in A} \pi(a \mid s) \left( R(s, a) + \gamma \sum_{s' \in S} P(s' \mid s, a) v_k(s') \right)$ $\pi' = \text{greedy}(V_\pi)$	Policy Iteration
Control	Bellman Optimality: $v_{k+1}(s) = \max_a \left( R(s, a) + \gamma \sum_{s' \in S} P(s' \mid s, a) v_k(s') \right)$	Value Iteration

Efficiency of DP​

• Strengths:
  • A foundational and efficient framework widely used for solving MDPs.
  • Mathematically guaranteed to converge to an optimal policy in polynomial time in terms of the number of states and actions.
  • Exponentially faster than exhaustive direct search across the policy space ($|A|^{|S|}$).
• Limitations:
  • Can become computationally impractical for extremely large or complex environments.
  • Curse of Dimensionality: As the number of state variables (dimensions) increases, the total state space size ($|S|$) expands exponentially, leading to severe computational and memory bottlenecks.

Asynchronous Dynamic Programming​

• Comparison with Synchronous Methods: Standard DP methods sweep through the entire state space systematically in every iteration. Asynchronous DP backs up individual states independently in arbitrary order.
• In-place Value Updates: Directly overwrites values in a single memory array, allowing immediate propagation of newly updated state values to subsequent calculations.
• Computational Gain & Convergence:
  • Significantly reduces computation by avoiding exhaustive full-state sweeps.
  • Guaranteed to converge to the optimal value function $v_*$, provided that all states continue to be selected and updated indefinitely.

Real-Time Dynamic Programming (RTDP)​

• Interaction-Driven Online Updates: Solves sub-problems on-the-fly by focusing updates specifically on states that are directly relevant to the agent's current trajectory.
• Target Applications: Large-scale environments where full state-space iteration is intractable (e.g., robotics, autonomous control systems, game AI).
• Core Characteristics:
  • Online Decision Making: Makes and refines decisions while operating directly in the environment.
  • Lazy Evaluation: Computes values only for visited or critical state subsets rather than unvisited distant states.
  • Adaptive Exploration: Guides search toward high-reward trajectories through active interaction.
  • Approximate MDP Solution: Yields near-optimal policies for relevant regions without solving the global MDP.

Approximate Dynamic Programming (ADP)​

• Motivation: Addresses the curse of dimensionality where tabular representation of states and exact value computation become computationally infeasible.
• Function Approximation Methods: Parameterizes and estimates the value function using scalable statistical and machine learning models:
  • Linear models, deep neural networks, decision trees, and general regression techniques.
• Error Management Mechanisms:
  • Eligibility Traces: Accelerates credit assignment and temporal consistency across multi-step transitions.
  • Experience Replay: Stores transition tuples in a replay buffer and samples them randomly to break data correlation and stabilize value approximation.

Bellman Equation​

$v_\pi(s) = \mathbb{E}_\pi \left[ \underbrace{R_{t+1}}_{\text{Immediate Reward}} + \gamma \underbrace{v_\pi(S_{t+1})}_{\text{Discounted Future Value}} \;\middle|\; \underbrace{S_t = s}_{\text{Starting at state s}} \right]$

• Fundamental concept in RL using a recursive equation to express a way to compute the value of a state based on the values of its successor states.

$$\begin{aligned} v(s) &= \mathbb{E} \left[ R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots \;\middle|\; S_t = s \right] \\[8pt] &= \mathbb{E} \left[ R_{t+1} + \gamma \underbrace{\left( R_{t+2} + \gamma R_{t+3} + \dots \right)}_{G_{t+1}} \;\middle|\; S_t = s \right] \\[8pt] &= \mathbb{E} \left[ R_{t+1} + \gamma G_{t+1} \;\middle|\; S_t = s \right] \\[8pt] &= \mathbb{E} \left[ R_{t+1} + \gamma v(S_{t+1}) \;\middle|\; S_t = s \right] \\[8pt] &= \underbrace{\mathbb{E}[R_{t+1} \mid S_t = s]}_{\text{Immediate Reward } \mathcal{R}(s)} + \gamma \, \underbrace{\mathbb{E}[v(S_{t+1}) \mid S_t = s]}_{\text{Expected Next State Value}} && (\because \mathbb{E}[X + \gamma Y] = \mathbb{E}[X] + \gamma\mathbb{E}[Y]) \\[10pt] &= \mathcal{R}(s) + \gamma \underbrace{\sum_{s'} \mathcal{P}(s' \mid s) v(s')}_{\text{Transition Dynamics}} && \left(\because \mathbb{E}[g(X)] = \sum_x P(x)g(x)\right) \end{aligned}$$

Bellman Equation Example​

$v(s_{\text{BL}}) = 7 + \gamma(0.1 \cdot v(s_{\text{BL}}) + 0.5 \cdot(s_{TL}) + 0.4 \cdot(s_{BR}))$

Bellman Equation in Matrix Form​

$v = \mathcal{R} + \gamma \mathcal{P} v$

$$\begin{aligned} \underbrace{ \begin{bmatrix} v(s_1) \\ \vdots \\ v(s_n) \end{bmatrix}}_{\text{V of a particular state}} = \underbrace{\begin{bmatrix} \mathcal{R}(s_1) \\ \vdots \\ \mathcal{R}(s_n) \end{bmatrix}}_{\text{Immediate Reward}} + \gamma \underbrace{\begin{bmatrix} \mathcal{P}_{11} & \cdots & \mathcal{P}_{1n} \\ \vdots & \ddots & \vdots \\ \mathcal{P}_{n1} & \cdots & \mathcal{P}_{nn} \end{bmatrix}}_{\text{Transition Matrix}} \underbrace{\begin{bmatrix} v(s_1) \\ \vdots \\ v(s_n) \end{bmatrix}}_{\text{V of future state}} \end{aligned}$$

Solving the Bellman Equation​

Linear System of Equations​

$$\begin{aligned} \mathcal{v} &= \mathcal{R} + \gamma \mathcal{P}\mathcal{v} \\ \mathcal{v} - \gamma \mathcal{P}\mathcal{v} &= \mathcal{R} \\ (I - \gamma \mathcal{P})\mathcal{v} &= \mathcal{R} \\ \mathcal{v} &= (I - \gamma \mathcal{P})^{-1} \mathcal{R} \end{aligned}$$

• Computational Complexity: $O(n^3)$
• For small MDPs: direct solution is possible (up to 100 states)
• For large MDPs:
  • Iterative methods
  • Dynamic Programming
  • Monte Carlo Tree
  • TD learning

State-Value Function​

$$\begin{aligned} \underbrace{v_\pi(s)}_{\text{Value of state } s} = \underbrace{\mathbb{E}_\pi}_{\text{Follows policy } \pi} \left[ \underbrace{R_{t+1}}_{\text{Immediate Reward}} + \gamma \underbrace{v_\pi(S_{t+1})}_{\text{Discounted Value of Next State}} \;\middle|\; \underbrace{S_t = s}_{\text{Starting at state } s} \right] \end{aligned}$$

• Evaluates the expected return starting from state $s$ and following policy $\pi$ thereafter.
• How good is it to be in state $s$?
• $v_\pi(s)$: Expected cumulative return starting from state $s$ under policy $\pi$.
• $\mathbb{E}_\pi$: Expectation over action selections ($A_t \sim \pi$) and transition dynamics ($S_{t+1} \sim \mathcal{P}$).
• $R_{t+1}$: Immediate reward received upon transitioning out of state $s$.
• $\gamma v_\pi(S_{t+1})$: Discounted expected value of the next successor state $S_{t+1}$.
• $S_t = s$: Condition that the agent starts at state $s$ at time step $t$.

$v_{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) q_{\pi}(s, a)$

• The value of state $s$ is the policy-weighted average of the values of all possible actions that can be taken from that state.
• $v_{\pi}(s)$: Expected cumulative return starting from state $s$ under policy $\pi$.
• $\pi(a \mid s)$: Probability of taking action $a$ in state $s$ under policy $\pi$.
• $q_{\pi}(s, a)$: Value of taking action $a$ in state $s$ under policy $\pi$.

Action-Value Function​

$$\begin{aligned} \underbrace{q_\pi(s, a)}_{\text{Action-Value of } (s, a)} = \underbrace{\mathbb{E}_\pi}_{\text{Follows policy } \pi} \left[ \underbrace{R_{t+1}}_{\text{Immediate Reward}} + \gamma \underbrace{q_\pi(S_{t+1}, A_{t+1})}_{\text{Discounted Next Action-Value}} \;\middle|\; \underbrace{S_t = s, A_t = a}_{\text{Starting at } s \text{ taking action } a} \right] \end{aligned}$$

• Evaluates the expected return of taking an arbitrary action $a$ in state $s$, and subsequently following policy $\pi$ from step $t+1$ onward.
• How good is it to take action $a$ in state $s$?
• $q_\pi(s, a)$: Value of taking action $a$ in state $s$ under policy $\pi$ (Q-value).
• $\mathbb{E}_\pi$: Expectation over the next transition ($S_{t+1} \sim \mathcal{P}$) and the subsequent action ($A_{t+1} \sim \pi$).
• $R_{t+1}$: Immediate reward resulting from the state-action pair $(s, a)$.
• $\gamma q_\pi(S_{t+1}, A_{t+1})$: Discounted expected value of the successor state-action pair $(S_{t+1}, A_{t+1})$.
• $S_t = s, A_t = a$: Condition that both the initial state and the initial action are fixed at time $t$.

$$\begin{aligned} v_\pi(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) \left( \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a v_\pi(s') \right) \end{aligned}$$

• Evaluates state $s$ directly by averaging over all possible action branches ($\pi$) and their subsequent environmental transitions ($\mathcal{P}$).
• $\mathcal{R}_s^a$: Immediate reward resulting from the state-action pair $(s, a)$.
• $\gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a v_\pi(s')$: Discounted expected value of the successor state $s'$ resulting from the state-action pair $(s, a)$.
• $\mathcal{P}_{ss'}^a$: Probability of transitioning from state $s$ to state $s'$ when action $a$ is taken.
• $\mathcal{S}$: Set of all possible states.
• $\mathcal{A}$: Set of all possible actions.
• $\pi(a \mid s)$: Probability of taking action $a$ in state $s$ under policy $\pi$.
• $v_\pi(s')$: Value of state $s'$ under policy $\pi$.

Bellman Expectation Equation​

$$\begin{aligned} q_\pi(s, a) = \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a \sum_{a' \in \mathcal{A}} \pi(a' \mid s') q_\pi(s', a') \end{aligned}$$

• Evaluates the state-action pair $(s, a)$ by summing immediate reward and the expected value of future action pairs $(s', a')$, averaged across transition dynamics $\mathcal{P}$ and next-step policy choices $\pi$.
• $\mathcal{R}_s^a$: Immediate reward resulting from the state-action pair $(s, a)$.
• $\gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a \sum_{a' \in \mathcal{A}} \pi(a' \mid s') q_\pi(s', a')$: Discounted expected value of the successor state-action pair $(s', a')$ resulting from the state-action pair $(s, a)$.
• $\mathcal{P}_{ss'}^a$: Probability of transitioning from state $s$ to state $s'$ when action $a$ is taken.
• $\mathcal{S}$: Set of all possible states.
• $\mathcal{A}$: Set of all possible actions.
• $\pi(a' \mid s')$: Probability of taking action $a'$ in state $s'$ under policy $\pi$.

$$\begin{matrix} v_\pi(s) & \xrightarrow{\text{Action Policy } \pi} & q_\pi(s, a) \\ \uparrow & & \downarrow \text{Environment Transition } \mathcal{P} \\ v_\pi(s') & \xleftarrow{\text{Environment Transition } \mathcal{P}} & q_\pi(s', a') \end{matrix}$$

Optimal Value Function​

$V_*(s) = \max_\pi v_\pi(s)$

• The optimal State-Value Function $V_*(s)$
• Maximum value function over all policies, or maximum possible reward that can be achieved from state $s$.

$q_*(s, a) = \max_\pi q_\pi(s, a)$

• The Optimal Action-Value Function $q_*(s, a)$
• Maximum action-value function over all policies, or given state $s$ and action taken $a$, what is the maximum reward that can be achieved from there onwards.

Optimal Policy​

$\pi_* \geq \pi \iff v_{\pi_*(s)} \geq v_\pi(s) \quad \forall s \in \mathcal{S}$

• If certain policy is better than another policy, then the value of the better policy is greater than or equal to the value of others in all states.

Theorem fo any MDP​

• Existence of an Optimal Policy: There always exists at least one optimal policy $\pi_*$ that is better than or equal to all other policies across all states ($\pi_* \ge \pi, \; \forall \pi$).
• Uniqueness of the Optimal State-Value Function: Although multiple distinct optimal policies may exist (e.g., when two different paths yield the exact same maximum expected return), all optimal policies achieve the exact same unique optimal state-value function ($v_{\pi_*}(s) = v_*(s)$).
• Uniqueness of the Optimal Action-Value Function: Similarly, all optimal policies achieve the exact same unique optimal action-value function ($q_{\pi_*}(s, a) = q_*(s, a)$).

Finding an Optimal Policy​

$$\pi_*(a \mid s) = \begin{cases} 1 & \text{if } a = \arg\max_{a \in \mathcal{A}} q_*(s, a) \\ 0 & \text{otherwise} \end{cases}$$

• If $q_*(s, a)$ is known, optimal policy is achieved.
• A deterministic optimal policy always exists for any MDP.

Bellman Optimality Equation​

Bellman Optimality Equation for $v_*$​

$$\begin{aligned} \underbrace{v_*(s)}_{\text{Optimal Value of State } s} = \max_{a \in \mathcal{A}} \underbrace{q_*(s, a)}_{\text{Optimal Value of Action } a} \end{aligned}$$

• State-Value to Action-Value ($s \rightarrow a$)
• The optimal state-value is achieved by greedily picking the single action that yields the maximum optimal action-value.

$$\begin{aligned} \underbrace{q_*(s, a)}_{\text{Optimal Action-Value}} = \underbrace{\mathcal{R}_s^a}_{\text{Immediate Reward}} + \gamma \underbrace{\sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a v_*(s')}_{\text{Expected Optimal Future Value}} \end{aligned}$$

• Action-Value to Next State-Value ($a \rightarrow s'$)
• Once the action $a$ is committed, the outcome is governed by the environment dynamics $\mathcal{P}_{ss'}^a$, requiring an expectation (average) over possible successor states $s'$.

$$\begin{aligned} \underbrace{v_*(s)}_{\text{Optimal Value of State } s} = \max_{a \in \mathcal{A}} \left( \underbrace{\mathcal{R}_s^a}_{\text{Immediate Reward}} + \gamma \underbrace{\sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a v_*(s')}_{\text{Expected Optimal Future Value}} \right) \end{aligned}$$

• Bellman Optimality Equation for $v_*$ ($s \rightarrow a \rightarrow s'$)
• Combines the agent's deterministic maximization ($\max_a$) with the environment's stochastic transition ($\sum_{s'} \mathcal{P}_{ss'}^a$).
  • It means a structure where the best choice I can make ($\max$) embeds the probabilistic outcomes of the world ($\sum$) in its calculation.
• Non-Linear System: Because of the $\max$ operator, this system of equations cannot be solved directly via matrix inversion $(I - \gamma\mathcal{P})^{-1}$
  • it must be solved iteratively via Dynamic Programming (Value Iteration) or Reinforcement Learning.

Bellman Optimality Equation for $q_*$​

$$\begin{aligned} \underbrace{q_*(s, a)}_{\text{Optimal Action-Value}} = \underbrace{\mathcal{R}_s^a}_{\text{Immediate Reward}} + \gamma \underbrace{\sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a}_{\text{Transition Dynamics}} \underbrace{\max_{a' \in \mathcal{A}} q_*(s', a')}_{\text{Optimal Successor Action}} \end{aligned}$$

• Bellman Optimality Equation for $q_*$ ($(s, a) \to s' \to a'$)
• Action Commitment: The initial state $s$ and action $a$ are fixed, receiving immediate reward $\mathcal{R}_s^a$.
• Stochastic Transition: The agent transitions to successor state $s'$ according to the environment's transition probability $\mathcal{P}_{ss'}^a$.
• Greedy Successor Action ($\max_{a'}$): Upon landing in state $s'$, the agent greedily selects the action $a'$ that yields the maximum possible optimal action-value $q_*(s', a')$.
• Core Foundation of Q-Learning: This equation directly forms the update target for off-policy algorithms like Q-Learning and DQN

Solving Bellman optimality equation​

• Non-Linear equation: The optimality equations embed the non-linear $\max$ operator, they cannot be linearized into standard matrix inversions.

Dynamic Programming Approaches​

$$\begin{aligned} \pi_{k+1}(s) = \arg\max_{a \in \mathcal{A}} \left[ \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a v_{\pi_k}(s') \right] \end{aligned}$$

• Policy Iteration: Alternates between full Policy Evaluation and Policy Improvement until the policy stabilizes ($\pi_{k+1} = \pi_k$).

$$\begin{aligned} v_{k+1}(s) \leftarrow \max_{a \in \mathcal{A}} \left[ \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a v_k(s') \right] \end{aligned}$$

• Value Iteration: Turns the Bellman Optimality Equation directly into an iterative update rule, bypassing explicit policy evaluation steps.

Temporal-Difference Control Approaches​

$$\begin{aligned} Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ \underbrace{R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a)}_{\text{Off-policy Target from } q_*} - Q(S_t, A_t) \right] \end{aligned}$$

• Q-Learning (Off-Policy TD Control): Learns optimal action-values $q_*$ directly from experience tuples $(S_t, A_t, R_{t+1}, S_{t+1})$ by approximating the Bellman Optimality Equation via bootstrapping.

$$\begin{aligned} Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ \underbrace{R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})}_{\text{On-policy Target from } q_\pi} - Q(S_t, A_t) \right] \end{aligned}$$

• SARSA (On-Policy TD Control): Learns action-values $q_\pi$ for the current policy from experience transitions $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$, steadily improving the policy toward optimality.

Policy Evaluation​

• Evaluate a given policy $\pi$ is a prediction problem.
• Iterative application of Bellman Expectation backup.

$$\begin{aligned} &\textbf{Input:} \\ &\quad \pi : \text{Policy to be evaluated} \\[6pt] &\textbf{Parameters:} \\ &\quad \theta > 0 : \text{Small threshold determining estimation accuracy} \\ &\quad \gamma \in [0, 1] : \text{Discount factor} \\[6pt] &\textbf{Initialize:} \\ &\quad V(s) \in \mathbb{R}, \quad \forall s \in \mathcal{S} \\ &\quad V(\text{terminal}) = 0 \\[8pt] &\textbf{Repeat:} \\ &\quad \Delta \leftarrow 0 \\ &\quad \textbf{For each } s \in \mathcal{S}: \\ &\quad\quad v \leftarrow V(s) \\ &\quad\quad V(s) \leftarrow \sum_{a \in \mathcal{A}} \pi(a \mid s) \left( \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a V(s') \right) \\ &\quad\quad \Delta \leftarrow \max \left( \Delta, \; |v - V(s)| \right) \\ &\textbf{Until } \Delta < \theta \\[8pt] &\textbf{Output:} \\ &\quad V \approx v_\pi \end{aligned}$$

• $\pi$: Target policy being evaluated ($\pi(a \mid s)$ is the action selection probability).
• $\theta$: Small threshold ($\theta > 0$) defining the stopping criterion for convergence.
• $\gamma$: Discount factor ($\gamma \in [0, 1]$) for future rewards.
• $V(s)$: Current estimated value of state $s$ (with $V(\text{terminal}) = 0$).
• $\Delta$: Maximum absolute value change across all states during the current sweep ($\max |v - V(s)|$).
• $\mathcal{R}_s^a$: Expected immediate reward from taking action $a$ in state $s$.
• $\mathcal{P}_{ss'}^a$: Transition probability to successor state $s'$ from state $s$ via action $a$.
• $v_\pi$: True state-value function under policy $\pi$ that $V(s)$ converges to.

Policy Improvement​

$$\begin{aligned} \pi'(s) = \arg\max_{a \in \mathcal{A}} \underbrace{\left[ \mathcal{R}_s^a + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'}^a V_\pi(s') \right]}_{q_\pi(s, a)} \end{aligned}$$

• Computing Value-function for a policy helps to find better policies.
• Evaluate the policy $\pi$, find $V_\pi(s)$
• Improve the policy by greedy action: $\pi' = \text{greedy}(V_\pi)$
• $\pi$: Current baseline policy before improvement.
• $V_\pi(s)$: True state-value function evaluated under policy $\pi$.
• $\pi'$: New, improved policy updated via greedy action selection.
• $\arg\max_{a}$: The operation of selecting the action $a$ that maximizes the subsequent expected return ($q_\pi(s, a)$).
• $\mathcal{R}_s^a$: Immediate expected reward earned by taking action $a$ in state $s$.
• $\gamma$: Discount factor ($\gamma \in [0, 1]$).
• $\mathcal{P}_{ss'}^a$: Transition probability to successor state $s'$ from state $s$ via action $a$.

Policy Iteration Algorithm​

Policy Iteration = Evaluate -> Improve -> Repeat

$$\begin{aligned} &\textbf{1. Initialization} \\ &\quad V(s) \in \mathbb{R} \text{ and } \pi(s) \in \mathcal{A}(s) \text{ arbitrarily for all } s \in \mathcal{S} \\[6pt] &\textbf{2. Policy Evaluation} \\ &\quad \textbf{Loop:} \\ &\quad\quad \Delta \leftarrow 0 \\ &\quad\quad \textbf{Loop for each } s \in \mathcal{S}: \\ &\quad\quad\quad v \leftarrow V(s) \\ &\quad\quad\quad V(s) \leftarrow \sum_{s', r} p(s', r \mid s, \pi(s)) \left[ r + \gamma V(s') \right] \\ &\quad\quad\quad \Delta \leftarrow \max \left( \Delta, \; |v - V(s)| \right) \\ &\quad \textbf{until } \Delta < \theta \quad \text{($\theta > 0$, small positive threshold)} \\[6pt] &\textbf{3. Policy Improvement} \\ &\quad \textit{policy-stable} \leftarrow \text{true} \\ &\quad \textbf{For each } s \in \mathcal{S}: \\ &\quad\quad \textit{old-action} \leftarrow \pi(s) \\ &\quad\quad \pi(s) \leftarrow \arg\max_{a \in \mathcal{A}(s)} \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma V(s') \right] \\ &\quad\quad \textbf{if } \textit{old-action} \neq \pi(s) \textbf{ then } \textit{policy-stable} \leftarrow \text{false} \\[4pt] &\quad \textbf{if } \textit{policy-stable} \textbf{ then stop and return } V \approx v_* \text{ and } \pi \approx \pi_* \\ &\quad \textbf{else go to 2} \end{aligned}$$

• Policy Evaluation (Prediction): What happens if I follow this policy?
• $V_\pi(s)$: How good is each state?
• $Q_\pi(s,a)$: What happens if I take an action $a$?
• Policy Improvement: Which action is better?
• Optimal Policy: Repeat until no change

• $\mathcal{R}(s_1) = 0.5(+10) + 0.1(+7) + 0.1(+5) + 0.3(0) = \mathbf{6.2}$
• $\mathcal{R}(s_2) = 0.5(0) + 0.1(0) + 0.4(-1) = \mathbf{-0.4}$
• $\mathcal{R}(s_3) = 0.5(0) + 0.5(0) = \mathbf{0}$
• $\mathcal{R}(s_4) = 0.3(0) + 0.2(0) + 0.5(0) = \mathbf{0}$
• $\mathcal{R}(s_5) = 0.3(0) + 0.7(-2) = \mathbf{-1.4}$

$$\begin{aligned} v(s_1) &= 6.2 + \gamma \left[ 0.1 v(s_2) + 0.5 v(s_3) + 0.1 v(s_4) \right] \quad (\because v(s_6) = 0) \\ v(s_2) &= -0.4 + \gamma \left[ 0.4 v(s_1) + 0.1 v(s_2) + 0.5 v(s_3) \right] \\ v(s_3) &= 0 + \gamma \left[ 0.5 v(s_2) + 0.5 v(s_3) \right] \\ v(s_4) &= 0 + \gamma \left[ 0.5 v(s_1) + 0.2 v(s_4) + 0.3 v(s_5) \right] \\ v(s_5) &= -1.4 + \gamma \left[ 0.7 v(s_1) + 0.3 v(s_5) \right] \end{aligned}$$ $$\begin{bmatrix} v(s_1) \\ v(s_2) \\ v(s_3) \\ v(s_4) \\ v(s_5) \end{bmatrix} = \left( \mathbf{I} - \gamma \begin{bmatrix} 0 & 0.1 & 0.5 & 0.1 & 0 \\ 0.4 & 0.1 & 0.5 & 0 & 0 \\ 0 & 0.5 & 0.5 & 0 & 0 \\ 0.5 & 0 & 0 & 0.2 & 0.3 \\ 0.7 & 0 & 0 & 0 & 0.3 \end{bmatrix} \right)^{-1} \begin{bmatrix} 6.2 \\ -0.4 \\ 0 \\ 0 \\ -1.4 \end{bmatrix}$$

$v(s_2) \left[ 1 - 0.1\gamma - \frac{0.5\gamma^2}{2 - \gamma} \right] = -0.4 + 0.4\gamma v(s_1)$