RL

Value Iteration combines policy improvement and a single step of policy evaluation into one operation.

• Initialization: Start with an arbitrary initial value for all states (e.g., \(v_0 = 0\)).
• Iteration:
  1. Implicit Policy Update: For all states, apply all possible action (Q-table), look ahead to find the best action. \[ \pi_{k+1} = \arg\max_{\pi} \left( r_{\pi} + \gamma P_{\pi} v_k \right) \]
  2. Value Update: Use that best action to update the state value immediately. \[ v_{k+1} = r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_k \]

Policy Iteration separates the process into two distinct phases. Crucially, the Policy Evaluation phase is itself an iterative process that looks very similar to Value Iteration, but with a fixed policy.

The mathematical connection is defined by the depth of the evaluation step (the number of iterations \(j\) in Phase 1):

• Value Iteration is a special case of Truncated Policy Iteration where the evaluation depth is \(j=1\).
• Policy Iteration is the limit of Truncated Policy Iteration where the evaluation depth \(j \to \infty\).

This is the simplest form, adapted directly from Policy Iteration logic but using sample returns instead of models.

• Theory:
  • Operates in strict distinct steps: Policy Evaluation (wait for many episodes) \(\rightarrow\) Policy Improvement (update policy).
  • Uses the Initial-Visit Strategy: Only the start of an episode is used to update the value of the starting state-action pair \((s_0, a_0)\). Intermediate steps in the episode are ignored for updates.
• Limitation:
  • Low Sample Efficiency: Wastes data by ignoring subsequent state visits in an episode.
  • Impractical: Requires collecting "sufficiently many episodes" for every state-action pair before making a single policy update.

An extension designed to fix sample efficiency but introduces a strong dependency on environment control.

• Theory:
  • Data Efficiency: Uses the Every-Visit Strategy (or sub-episode decomposition). One long episode is broken down into multiple "sub-episodes" to update values for every state visited, not just the start.
  • Episode-by-Episode Update: Updates the policy immediately after a single episode (Generalized Policy Iteration), rather than waiting for a batch.
• Limitation:
  • The "Exploring Starts" Assumption: It requires the environment to be able to start an episode at any random state-action pair \((s, a)\).
  • Real-world Friction: This is often impossible in physical reality (e.g., you cannot initialize a robot in a specific "falling over" state instantly).

This method removes the unrealistic "Exploring Starts" assumption, making MC methods viable for real-world learning where you cannot control the starting state.

• The Goal: Bellman Expectation Equation We seek \(V_{\pi}(s)\) such that: \[V_{\pi}(s) = \mathbb{E}_{\pi} [ R_{t+1} + \gamma V_{\pi}(S_{t+1}) \mid S_t = s ]\]
• The Problem: Root Finding Define the objective function (Bellman Error) \(J(V)\), where we want the root \(J(V)=0\): \[J(V)(s) = \mathbb{E} [ R_{t+1} + \gamma V(S_{t+1}) ] - V(s) = 0\]
• The Solver: Robbins-Monro Algorithm Iteratively find root \(\theta^*\) of \(f(\theta)=0\) using noisy observations \(\tilde{f}(\theta)\): \[\theta_{t+1} = \theta_t + \alpha_t \cdot \tilde{f}(\theta_t)\]
  • \(\theta\) > \(\theta^*\) minus \(\tilde{f}(\theta_t)\)
  • \(\theta\) < \(\theta^*\) plus \(\tilde{f}(\theta_t)\)

• The Noisy Observation (TD Error) Since we cannot compute the expectation \(\mathbb{E}\), we take a single sample:
  • Observation: \(\tilde{J}(V_t) = (r_{t+1} + \gamma V_t(s_{t+1})) - V_t(s_t)\)
  • This is the TD Error (\(\delta_t\)).
• The Sample Target The term \(r_{t+1} + \gamma V_t(s_{t+1})\) acts as the "Label":
  • Reality: \(r_{t+1}\) (Ground truth, low variance).
  • Guess: \(\gamma V_t(s_{t+1})\) (Bootstrap estimate).
  • Function: It acts as the target \(y\) for \(V(s_t)\), providing a better estimate than \(V(s_t)\) alone because it includes real data.
• The Solution (TD Update Rule) Substituting \(\tilde{f}(\theta)\) into the Robbins-Monro update: \[V(s_t) \leftarrow V(s_t) + \alpha \delta_t\] \[V(s_t) \leftarrow V(s_t) + \alpha \underbrace{[ (r_{t+1} + \gamma V(s_{t+1})) - V(s_t) ]}_{\text{TD Error}}\] \[V(s_t) \leftarrow V(s_t) - \alpha [ V(s_t) - \underbrace{(r_{t+1} + \gamma V(s_{t+1}))}_{\text{Target}} ]\]

• Deep Q-learning replaces the tabular \(q(s,a)\) with a parameterized neural network \(\hat{q}(s, a, w)\).
• We want the neural network to satisfy the Bellman Optimality Equation: \[q_*(s, a) = \mathbb{E} [R_{t+1} + \gamma \max_{a'} q_*(S_{t+1}, a') \mid S_t=s, A_t=a]\]
• It aims to minimize the loss function \(J(w)\): \[J(w) = \mathbb{E} \left[ \left( \underbrace{R + \gamma \max_{a' \in \mathcal{A}(S')} \hat{q}(S', a', w)}_{\text{Target (Bellman Optimality)}} - \underbrace{\hat{q}(S, A, w)}_{\text{Prediction}} \right)^2 \right]\]

where The term inside the squared brackets is the TD Error (specifically for Q-Learning). \[\delta = (R + \gamma \max \hat{q}(S', a', w)) - \hat{q}(S, A, w)\]. In order to minimize the distance (error) between the Prediction and the Target, the network \(\hat{q}\) converges towards the optimal value function \(q_*\).

• Algorithm
  • Sample: Uniformly draw a mini-batch of samples from \(\mathcal{B}\).
  • Calculate Targets: For each sample \((s, a, r, s')\) in the mini-batch, calculate the target value \(y_T\): \[y_T = r + \gamma \max_{a \in \mathcal{A}(s')} \hat{q}(s', a, w_T)\]
    • Where \(w_T\) is the parameter of the target network.
  • Update Main Network: Update the main network parameter \(w\) to minimize the loss: \[Loss = (y_T - \hat{q}(s, a, w))^2\]
    • This update uses the mini-batch data \(\{(s, a, y_T)\}\).
  • Update Target Network: Set \(w_T = w\) every \(C\) iterations.

• \(\bar{v}_\pi\) (Discounted Average Value) \[\sum_{s \in S} d(s)\, v_\pi(s)\] \[\mathbb{E}_{S \sim d}[v_\pi(S)]\] \[\mathbb{E}\left[\sum_{t=0}^{\infty} \gamma^{t} R_{t+1}\right]\]
• \(\bar{r}_\pi\) (Average Reward Objective) \[\sum_{s \in S} d_\pi(s)\, r_\pi(s)\] \[\mathbb{E}_{S \sim d_\pi}[r_\pi(S)]\] \[\lim_{n \to \infty} \frac{1}{n} \mathbb{E}\left[\sum_{t=0}^{n-1} R_{t+1}\right]\]

The gradient of the objective function \(J(\theta)\) is given by the Policy Gradient Theorem: \[\nabla_\theta J(\theta) = \sum_{s \in S} \eta(s) \sum_{a \in A} \nabla_\theta \pi(a \mid s, \theta)\, q_\pi(s, a)\]

where:

• \(\eta(s)\) is the state distribution (discounted or stationary depending on metric)
• \(\nabla_\theta \pi(a \mid s, \theta)\) denotes the gradient of the policy \(\pi\) with respect to the parameters \(\theta\),
• \(q_\pi(s, a)\) is the action-value function.
• Note: The theorem proves equality, but in practice, ignoring the gradient of the state distribution leads to an approximation often called the "proportional" gradient.

Moreover, as an expectation:\[ \nabla_\theta J(\theta) = \mathbb{E}_{S \sim \eta,\; A \sim \pi(S,\theta)} \left[ \nabla_\theta \ln \pi(A \mid S, \theta)\, q_\pi(S, A) \right].\]

\[ \theta_{t+1} = \theta_t + \alpha \nabla_\theta J(\theta_t)\]

Using the expectation form of the policy gradient, this becomes:

\[\theta_{t+1} = \theta_t + \alpha \mathbb{E} [ \nabla_\theta \ln \pi(A \mid S, \theta_{t})\, q_{\pi}(S, A) ]\]

We do not have \(q_{\pi}(S, A)\), so use \(\hat{q}(S_t, A_t)\) from sampling. \[\theta_{t+1} = \theta_t + \alpha \nabla_\theta \ln \pi(A_t \mid S_t, \theta_t)\, \hat{q}(S_t, A_t)\]

• Sampling from MC: REINFORCE
• Sampling from TD: Actor-Critic

\[\theta_{t+1} = \theta_t + \alpha \nabla_{\theta} \ln \pi(a_t \mid s_t, \theta_t) q_t(s_t, a_t)\] Because of the log-derivative trick: \[\nabla_{\theta} \ln \pi(a_t \mid s_t, \theta_t) = \frac{\nabla_{\theta} \pi(a_t \mid s_t, \theta_t)}{\pi(a_t \mid s_t, \theta_t)}\] We have: \[\theta_{t+1} = \theta_t + \alpha \frac{\nabla_{\theta} \pi(a_t \mid s_t, \theta_t)}{\pi(a_t \mid s_t, \theta_t)} q_t(s_t, a_t)\] So, defining \(\beta_t = \frac{q_t(s_t, a_t)}{\pi(a_t \mid s_t, \theta_t)}\): \[\theta_{t+1} = \theta_t + \alpha \beta_t \nabla_{\theta} \pi(a_t \mid s_t, \theta_t)\]

• If \(\beta_t \ge 0 \implies\) Move in direction of gradient:
  • -\(\implies \pi(a_t | s_t, \theta_{t+1}) \ge \pi(a_t | s_t, \theta_t)\)
  • Enhancement
  • Reinforce good actions
• If \(\beta_t < 0 \implies\) Move opposite to gradient :
  • \(\implies \pi(a_t | s_t, \theta_{t+1}) < \pi(a_t | s_t, \theta_t)\)
  • Decrease
  • Suppress bad actions

Monte Carlo Policy Gradient

• Initialize: \(\theta\), \(\gamma \in (0,1)\), \(\alpha > 0\)

• Loop for each episode:

  • Generate episode \(\{s_0, a_0, r_1, \dots, s_{T-1}, a_{T-1}, r_T\}\) following policy \(\pi(\cdot|\cdot, \theta_k)\)
  • For \(t = 0\) to \(T-1\):
    • \(G_t \leftarrow \sum_{k=t+1}^{T} \gamma^{k-t-1} r_k\) (Calculate return)
    • \(\theta_{t} \leftarrow \theta_{t} + \alpha \gamma^t G_t \nabla_{\theta} \ln \pi(a_t | s_t, \theta_{k})\)
  • \(\theta_{k} \leftarrow \theta_{t}\)

We use a behavior policy \(\beta\) to generate experience samples. To estimate the gradient of the target policy \(\pi\), we must use Importance Sampling.

The Actor and Critic optimize fundamentally conflicting objectives, leading to Catastrophic Forgetting in shared architectures.

• Gradient Wash-Out: The Critic's gradients can "wash out" the delicate weights required for language generation.
• Manifold Collapse: When the model maximizes reward aggressively, it loses coherence, causing catastrophic forgetting of the pre-trained language manifold.

Shared weights prevent the necessary decoupling of learning dynamics between the two heads.

• The Critic (Fast Learner): Requires rapidly tracking non-stationary value targets (\(V(s)\) changes constantly as \(\pi\) evolves).
• The Actor (Slow Learner): Requires strict constraints (Trust Region/Clipping) to ensure monotonic improvement.
• The Conflict: In a shared body, you cannot tune optimizers independently. A learning rate high enough for the Critic destabilizes the Actor; a rate low enough for the Actor starves the Critic.

Separating policy and value function training into distinct phases PPG.

We reject GRPO (which requires generating groups for a baseline). Instead, we use Time as our baseline.

We use a single Transformer. The MTP Modules (which normally predict future tokens) are slightly modified to also predict the Value (Expected Future Reward) of those tokens.

• No Separate Critic Network: The MTP heads are the Critic.
• No Group Sampling: We do not compare against a group average. We compare against our own prediction from the next step (Bootstrapping).
• One Network: Parameters \(\theta\) are shared.

Standard DeepSeek MTP predicts tokens \(t_{n+1}, t_{n+2} \dots\). We modify the output projection of the MTP modules to output two things:

1. Token Logits: \(P(t_{n+k})\) (What happens next?)
2. Scalar Value: \(V_{n+k}\) (How good is it?)

Equation: \[ [ \text{Logits}_{k}, v_{k} ] = \text{MTP Head}_k(h_n) \] Where \(v_k\) represents the expected return starting from step \(n+k\).

1. Single Network: The Policy and Value are fused. The "Value" is just a tiny scalar output on the existing MTP heads.
2. No GRPO: We don't need multiple samples to find a baseline. We use the Bellman Consistency (\(V_t \approx r + V_{t+1}\)) as the training signal.
3. MTP Integration: The MTP heads are essential. They provide the "Lookahead" capability that stabilizes the single-network value estimation (reducing the noise of a single step).
4. Internal Value Saved: The training relies on carrying the scalar \(v\) from step \(t+1\) backward to step \(t\).