RL 004

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)$