Value Function Estimation

The gradient of the policy is given by:

$$
 \frac{1}{m} \sum_{i=1}^m \sum_{t=0}^{H-1} \nabla_\theta \log \pi_\theta\left(u_t^{(i)} \mid s_t^{(i)}\right) \left( \sum_{k=t}^{H-1} R\left(s_k^{(i)}, u_k^{(i)}\right) - V^\pi\left(s_t^{(i)}\right) \right) 
$$

• m: Number of trajectories collected during rollouts.
• H: Horizon (number of steps in an episode).
• R(s_t, a_t): Reward received at state s_t after taking action a_t.
• V^π(s_t): Estimated value function, serving as a baseline.

Purpose of the Baseline V^π(s_t): reduces variance in the gradient estimate without altering its expectation.

3b. Estimating the Value Function

To estimate V^π(s), we use a regression method based on collected trajectories.

1. Initialization: Initialize the value function V_ϕ^π(s) as a neural network parameterized by ϕ.

2. Trajectory Collection: Gather trajectories {τ₁,…,τ_m} by rolling out the current policy π_θ​.

3. Regression Against Empirical Returns:

   • For each state s_t⁽ⁱ⁾​, compute the Monte Carlo return R_t⁽ⁱ⁾​, which is the cumulative reward from time step $t$:

     $$
      R_t^{(i)} = \sum_{k=t}^{H-1} R\left(s_k^{(i)}, u_k^{(i)}\right) 
     $$

   • Fit V_ϕ^π(s) by minimizing the squared error between the estimated value function and the Monte Carlo returns:
     $$
      \phi_{i+1} \leftarrow \arg \min_\phi \frac{1}{m} \sum_{i=1}^m \sum_{t=0}^{H-1} \left( V^\pi_\phi\left(s_t^{(i)}\right) - G_t^{(i)} \right)^2 
     $$

3c. Algorithm Summary

• Input: Initial policy π_θ​, value function V_ϕ^π​, number of trajectories $m$, horizon $H$.
• Steps:
  1. Initialize V_ϕ^π
  2. Collect m trajectories τ₁,…,τ_m​ using π_θ​.
  3. Compute Monte Carlo returns G_t⁽ⁱ⁾ for all $t,i$.
  4. Update ϕ by minimizing the regression loss.
  5. Repeat for subsequent updates of π_θ​.

4. Bootstrap Value Function Estimation

The Bootstrap Estimation method utilizes the Bellman Equation for policy evaluation to estimate the value function V^π(s). This iterative approach, often referred to as "bootstrapping" combines sampled transitions and dynamic programming principles to approximate the value of states effectively.

4a. Key Concepts

1. Bellman Equation: The value of a state s under a policy π is calculated as the expected immediate reward plus the discounted value of the next state:

   $$
    V^\pi(s) = \sum_u \pi(u \mid s) \sum_{s'} P(s' \mid s, u) \left[ R(s, u, s') + \gamma V^\pi(s') \right] 
   $$
   
   • π(u∣s): Probability of taking action u in state s.
   • P(s′∣s,u): Transition probability from state s to s′ given action u.
   • R(s,u,s′): Reward received after transitioning to state s′.
   • γ: Discount factor that weighs future rewards.

2. Data Collection: Collect transition samples (s,u,s′,r), which include:

   • Current state s.
   • Action u taken.
   • Next state s′.
   • Reward r observed.

3. Fitted Value Iteration: Update the parameters $\varphi$ of the value function V_ϕ^π(s) iteratively. The parameters are optimized by minimizing the following loss function:

   $$
   \phi_{i+1} \leftarrow \arg \min_\phi \sum_{(s, u, s', r)} \left\| r + \gamma V_\phi^\pi(s') - V_\phi^\pi(s) \right\|_2^2 + \lambda \| \phi - \phi_i \|_2^2
   $$​
   • The first term minimizes the error in the Bellman equation.
   • The regularization term (λ∥ϕ−ϕ_i∥²₂) prevents drastic parameter updates.

4b. Purpose and Advantages

This approach bootstraps the value function by iteratively refining it based on sampled transitions. It effectively balances:

• Dynamic Programming (by leveraging the Bellman equation).
• Data-Driven Updates (using collected samples). This makes the method suitable for large-scale problems, where exact solutions are computationally infeasible.

5. Summary

Value functions lie at the heart of reinforcement learning, enabling agents to evaluate and optimize policies by estimating the expected cumulative rewards.

• Monte Carlo Estimation: This approach estimates value functions based on empirical returns from sampled trajectories, offering a variance-reduction mechanism for policy gradient methods and stabilizing the learning process.

• Bootstrap Estimation: By leveraging the Bellman equation, bootstrap methods iteratively refine value function estimates using sampled transitions, combining dynamic programming with data-driven updates for scalability and efficiency.

Together, these methods highlight the importance of value functions in improving policy evaluation and optimization, setting the stage for advanced reinforcement learning techniques. The concepts covered here provide a robust foundation for tackling more sophisticated algorithms introduced in subsequent lessons.