Reinforcement Learning Theory

1. Markov Decision Process (MDP) Formalism

An MDP is defined by the tuple :

• : State space
• : Action space
• : Transition dynamics
• : Reward function
• : Discount factor

1.1 Trajectory Distribution

A trajectory has probability:

1.2 Return and Discounted Return

The return from time step :

2. MDP Transition Diagram

<svg viewBox="0 0 800 400" xmlns="http://www.w3.org/2000/svg">
  <rect width="800" height="400" fill="#f8fafc"/>
  
  {/* Title */}
  <text x="400" y="30" text-anchor="middle" fill="#f8fafc" font-family="monospace" font-size="16" font-weight="bold">Markov Decision Process</text>
  
  {/* States */}
  <circle cx="150" cy="200" r="40" fill="#f8fafc" stroke="#3b82f6" stroke-width="3"/>
  <text x="150" y="195" text-anchor="middle" fill="#60a5fa" font-family="monospace" font-size="12" font-weight="bold">s₀</text>
  <text x="150" y="215" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">State</text>
  
  <circle cx="350" cy="150" r="40" fill="#f8fafc" stroke="#a855f7" stroke-width="3"/>
  <text x="350" y="145" text-anchor="middle" fill="#c084fc" font-family="monospace" font-size="12" font-weight="bold">s₁</text>
  <text x="350" y="165" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">State</text>
  
  <circle cx="350" cy="250" r="40" fill="#f8fafc" stroke="#22c55e" stroke-width="3"/>
  <text x="350" y="245" text-anchor="middle" fill="#22c55e" font-family="monospace" font-size="12" font-weight="bold">s₂</text>
  <text x="350" y="265" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">State</text>
  
  <circle cx="550" cy="200" r="40" fill="#f8fafc" stroke="#f59e0b" stroke-width="3"/>
  <text x="550" y="195" text-anchor="middle" fill="#fbbf24" font-family="monospace" font-size="12" font-weight="bold">s₃</text>
  <text x="550" y="215" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">Terminal</text>
  
  {/* Agent */}
  <g transform="translate(150, 120)">
    <rect width="60" height="30" rx="5" fill="#ec4899"/>
    <text x="30" y="20" text-anchor="middle" fill="white" font-family="monospace" font-size="10" font-weight="bold">Agent</text>
  </g>
  
  {/* Arrows: Actions */}
  <defs>
    <marker id="4062_arrowBlue" markerWidth="10" markerHeight="7" refX="9" refY="3.5" orient="auto">
      <polygon points="0 0, 10 3.5, 0 7" fill="#3b82f6"/>
    </marker>
    <marker id="4062_arrowPurple" markerWidth="10" markerHeight="7" refX="9" refY="3.5" orient="auto">
      <polygon points="0 0, 10 3.5, 0 7" fill="#a855f7"/>
    </marker>
    <marker id="4062_arrowGreen2" markerWidth="10" markerHeight="7" refX="9" refY="3.5" orient="auto">
      <polygon points="0 0, 10 3.5, 0 7" fill="#22c55e"/>
    </marker>
    <marker id="4062_arrowYellow" markerWidth="10" markerHeight="7" refX="9" refY="3.5" orient="auto">
      <polygon points="0 0, 10 3.5, 0 7" fill="#f59e0b"/>
    </marker>
  </defs>
  
  {/* Transition s₀ → s₁ */}
  <line x1="185" y1="185" x2="305" y2="155" stroke="#3b82f6" stroke-width="2" marker-end="url(#4062_arrowBlue)"/>
  <text x="240" y="160" text-anchor="middle" fill="#60a5fa" font-family="monospace" font-size="10">a₀, P(s₁|s₀,a₀)</text>
  
  {/* Transition s₀ → s₂ */}
  <line x1="185" y1="215" x2="305" y2="245" stroke="#a855f7" stroke-width="2" marker-end="url(#4062_arrowPurple)"/>
  <text x="240" y="240" text-anchor="middle" fill="#c084fc" font-family="monospace" font-size="10">a₁, P(s₂|s₀,a₁)</text>
  
  {/* Transition s₁ → s₃ */}
  <line x1="385" y1="150" x2="505" y2="190" stroke="#22c55e" stroke-width="2" marker-end="url(#4062_arrowGreen2)"/>
  <text x="440" y="160" text-anchor="middle" fill="#22c55e" font-family="monospace" font-size="10">r₁=10, γ=0.99</text>
  
  {/* Transition s₂ → s₃ */}
  <line x1="385" y1="250" x2="505" y2="210" stroke="#f59e0b" stroke-width="2" marker-end="url(#4062_arrowYellow)"/>
  <text x="440" y="245" text-anchor="middle" fill="#fbbf24" font-family="monospace" font-size="10">r₂=5, γ=0.99</text>
  
  {/* Policy */}
  <g transform="translate(50, 300)">
    <rect width="200" height="70" rx="8" fill="#f8fafc" stroke="#334155"/>
    <text x="100" y="20" text-anchor="middle" fill="#60a5fa" font-family="monospace" font-size="11" font-weight="bold">Policy π(a|s)</text>
    <text x="100" y="40" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">π(a₀|s₀) = 0.7</text>
    <text x="100" y="55" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">π(a₁|s₀) = 0.3</text>
  </g>
  
  {/* Value Function */}
  <g transform="translate(300, 300)">
    <rect width="200" height="70" rx="8" fill="#f8fafc" stroke="#334155"/>
    <text x="100" y="20" text-anchor="middle" fill="#a855f7" font-family="monospace" font-size="11" font-weight="bold">Value V(s)</text>
    <text x="100" y="40" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">V(s₀) = 7.43</text>
    <text x="100" y="55" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">V(s₁) = 10.0</text>
  </g>
  
  {/* Q-Value */}
  <g transform="translate(550, 300)">
    <rect width="200" height="70" rx="8" fill="#f8fafc" stroke="#334155"/>
    <text x="100" y="20" text-anchor="middle" fill="#22c55e" font-family="monospace" font-size="11" font-weight="bold">Q(s,a)</text>
    <text x="100" y="40" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">Q(s₀,a₀) = 9.9</text>
    <text x="100" y="55" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">Q(s₀,a₁) = 4.95</text>
  </g>
</svg>

3. Bellman Equations

3.1 Bellman Expectation Equation

For a policy , the state-value function:

The Bellman expectation equation:

Or more compactly:

3.2 Action-Value Function

The relationship:

3.3 Bellman Optimality Equation

The optimal value function:

3.4 Generalized Policy Iteration (GPI)

交替进行策略评估和策略改进：

4. Policy Gradient Theorem

4.1 The Objective

The objective is the expected return:

4.2 Policy Gradient Theorem (Sutton et al., 1999)

Proof sketch (log-derivative trick):

4.3 Advantage Formulation

The advantage function:

The policy gradient with baseline:

4.4 Causality and GAE

Generalized Advantage Estimation (Schulman et al., 2016):

where is the TD error.

5. Proximal Policy Optimization (PPO)

5.1 Clipped Surrogate Objective

where is the probability ratio.

5.2 PPO Full Objective

where:

• is the value function loss
• is the entropy bonus

5.3 PPO Pseudocode

def ppo_update(policy, value_fn, episodes, clip_eps=0.2):
    states, actions, returns, advantages = compute_gae(episodes)
    
    for epoch in range(K):  # K epochs
        for batch in minibatch(states, actions, returns, advantages):
            # Policy loss
            ratio = policy(batch.s, batch.a) / policy_old(batch.s, batch.a)
            clipped = torch.clamp(ratio, 1 - clip_eps, 1 + clip_eps)
            policy_loss = -torch.min(ratio * batch.adv, 
                                      clipped * batch.adv).mean()
            
            # Value loss
            value_pred = value_fn(batch.s)
            value_loss = F.mse_loss(value_pred, batch.ret)
            
            # Entropy bonus
            entropy = policy.entropy(batch.s).mean()
            
            loss = policy_loss + 0.5 * value_loss - 0.01 * entropy
            loss.backward()
            optimizer.step()

6. Soft Actor-Critic (SAC)

6.1 Maximum Entropy Objective

where is the entropy.

6.2 Soft Bellman Equation

6.3 Soft Policy Iteration

Soft Policy Evaluation:

Soft Policy Improvement:

The optimal policy is:

7. Policy Gradient Landscape

<svg viewBox="0 0 800 400" xmlns="http://www.w3.org/2000/svg">
  <rect width="800" height="400" fill="#f8fafc"/>
  
  {/* Title */}
  <text x="400" y="30" text-anchor="middle" fill="#f8fafc" font-family="monospace" font-size="16" font-weight="bold">Policy Gradient Methods</text>
  
  {/* Policy Gradient Theorem */}
  <g transform="translate(30, 50)">
    <rect width="350" height="150" rx="8" fill="#f8fafc" stroke="#3b82f6" stroke-width="2"/>
    <text x="175" y="25" text-anchor="middle" fill="#60a5fa" font-family="monospace" font-size="12" font-weight="bold">Policy Gradient Theorem</text>
    
    <text x="15" y="55" fill="#f8fafc" font-family="monospace" font-size="10">∇J(πθ) = Eτ~πθ [Σt ∇θ log πθ(at|st) · Gt]</text>
    
    <text x="15" y="80" fill="#22c55e" font-family="monospace" font-size="10">With baseline:</text>
    <text x="15" y="100" fill="#f8fafc" font-family="monospace" font-size="10">∇J(πθ) = Eτ~πθ [Σt ∇θ log πθ(at|st) · Â(st,at)]</text>
    
    <text x="15" y="125" fill="#f59e0b" font-family="monospace" font-size="10">Where Â(st,at) = Qπ(st,at) - Vπ(st)</text>
    
    <text x="15" y="145" fill="#a855f7" font-family="monospace" font-size="10">GAE: Ât = Σl (γλ)l δt+l</text>
  </g>
  
  {/* PPO Clipped Objective */}
  <g transform="translate(420, 50)">
    <rect width="350" height="150" rx="8" fill="#f8fafc" stroke="#a855f7" stroke-width="2"/>
    <text x="175" y="25" text-anchor="middle" fill="#c084fc" font-family="monospace" font-size="12" font-weight="bold">PPO Clipped Objective</text>
    
    <text x="15" y="55" fill="#f8fafc" font-family="monospace" font-size="10">LCLIP(θ) = Et[min(rt(θ)At,</text>
    <text x="15" y="95" fill="#f8fafc" font-family="monospace" font-size="10">    clip(rt(θ), 1-ε, 1+ε)At)]</text>
    
    <text x="15" y="100" fill="#22c55e" font-family="monospace" font-size="10">rt(θ) = πθ(at|st) / πθold(at|st)</text>
    
    <text x="15" y="125" fill="#f59e0b" font-family="monospace" font-size="10">ε = 0.2 (typical)</text>
    
    <text x="15" y="145" fill="#ec4899" font-family="monospace" font-size="10">Prevents large policy updates</text>
  </g>
  
  {/* Actor-Critic Architecture */}
  <g transform="translate(30, 220)">
    <rect width="740" height="160" rx="8" fill="#f8fafc" stroke="#22c55e" stroke-width="2"/>
    <text x="370" y="25" text-anchor="middle" fill="#22c55e" font-family="monospace" font-size="12" font-weight="bold">Actor-Critic Architecture</text>
    
    {/* Actor */}
    <rect x="50" y="50" width="150" height="100" rx="8" fill="#f8fafc" stroke="#3b82f6" stroke-width="2"/>
    <text x="125" y="75" text-anchor="middle" fill="#60a5fa" font-family="monospace" font-size="11" font-weight="bold">Actor (Policy)</text>
    <text x="125" y="100" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">πθ(a|s)</text>
    <text x="125" y="120" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">Outputs: actions</text>
    <text x="125" y="140" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">Loss: policy gradient</text>
    
    {/* Critic */}
    <rect x="250" y="50" width="150" height="100" rx="8" fill="#f8fafc" stroke="#a855f7" stroke-width="2"/>
    <text x="325" y="75" text-anchor="middle" fill="#c084fc" font-family="monospace" font-size="11" font-weight="bold">Critic (Value)</text>
    <text x="325" y="100" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">Vφ(s)</text>
    <text x="325" y="120" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">Outputs: value est.</text>
    <text x="325" y="140" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">Loss: MSE(G, V)</text>
    
    {/* Environment */}
    <rect x="500" y="50" width="150" height="100" rx="8" fill="#f8fafc" stroke="#f59e0b" stroke-width="2"/>
    <text x="575" y="75" text-anchor="middle" fill="#fbbf24" font-family="monospace" font-size="11" font-weight="bold">Environment</text>
    <text x="575" y="100" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">P(s'|s,a), R(s,a)</text>
    <text x="575" y="120" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">State transitions</text>
    <text x="575" y="140" text-anchor="middle" fill="#94a3b8" font-family="monospace" font-size="9">Reward signal</text>
    
    {/* Arrows */}
    <line x1="200" y1="100" x2="250" y2="100" stroke="#60a5fa" stroke-width="2" marker-end="url(#arrowBlue)"/>
    <line x1="400" y1="100" x2="500" y2="100" stroke="#fbbf24" stroke-width="2" marker-end="url(#arrowYellow)"/>
    <line x1="500" y1="120" x2="400" y2="120" stroke="#c084fc" stroke-width="2" marker-end="url(#arrowPurple)"/>
  </g>
  
  <defs>
    <marker id="4062_arrowBlue2" markerWidth="10" markerHeight="7" refX="9" refY="3.5" orient="auto">
      <polygon points="0 0, 10 3.5, 0 7" fill="#60a5fa"/>
    </marker>
    <marker id="4062_arrowPurple2" markerWidth="10" markerHeight="7" refX="9" refY="3.5" orient="auto">
      <polygon points="0 0, 10 3.5, 0 7" fill="#c084fc"/>
    </marker>
    <marker id="4062_arrowGreen3" markerWidth="10" markerHeight="7" refX="9" refY="3.5" orient="auto">
      <polygon points="0 0, 10 3.5, 0 7" fill="#22c55e"/>
    </marker>
    <marker id="4062_arrowYellow2" markerWidth="10" markerHeight="7" refX="9" refY="3.5" orient="auto">
      <polygon points="0 0, 10 3.5, 0 7" fill="#fbbf24"/>
    </marker>
  </defs>
</svg>

8. Model-Based Reinforcement Learning

8.1 Dyna Architecture

在 Dyna 中，agent 同时学习：

1. 真实环境经验:
2. 模型生成经验:

8.2 Model Predictive Control (MPC)

8.3 World Models

World Models (Ha & Schmidhuber, 2018):

8.4 MuZero

MuZero (Schrittwieser et al., 2020) learns:

1. Representation:
2. Dynamics:
3. Prediction:

9. Offline Reinforcement Learning

9.1 Conservative Q-Learning (CQL)

9.2 Decision Transformer

将 RL 视为序列建模问题。

10. Summary of Key Algorithms

Reinforcement learning theory provides the mathematical foundation for understanding how agents learn to make sequential decisions. The policy gradient theorem, Bellman equations, and actor-critic frameworks form the core of modern RL algorithms.