1. Introduction: From Actor-Critic to Value-Based RL

In Actor-Critic methods, we learned two functions: a policy ${\pi }_{\theta }$ (actor) and a value function $V_{\varphi }$ (critic). Value-Based Methods ask: Can we omit the explicit policy entirely?

The core idea is to define the policy implicitly using the value function. If we know the optimal value function $Q^{\ast }(s,a)$, the optimal policy is simply to establish the "greedy" action at every step:

This guarantees the policy is at least as good as the one that generated the values.

2. Foundations & Definitions

To understand Value-Based RL, we must rigorously define our objective and the equations we solve.

2.1 The Objective: Optimal Value

We define $Q^{\ast }(s,a)$ as the maximum expected total discounted reward starting from state $s$, taking action $a$, and acting optimally thereafter:

2.2 The Recursive Logic (Bellman Equation)

This definition implies a recursive relationship. The value of the current step is the immediate reward plus the discounted value of the best possible future.

Why is $V^{\ast }(s^{\prime })={\max }_{a^{\prime }}{Q}^{\ast }(s^{\prime },a^{\prime })$?

Since $V^{\ast }(s^{\prime })$ represents the value of being in state $s^{\prime }$ and acting optimally thereafter, the agent will choose the action $a^{\prime }$ that maximizes the expected return. Thus, the value of the state is the specific value of the best action available in that state.

Bellman Optimality Equation:

2.3 Requirements for Validity

For this recursive equation to hold, we assume:

1. Markov Property: Future depends only on $s$, not history.
2. Stationarity: Dynamics $p(s^{\prime }|s,a)$ and rewards $r(s,a)$ are constant.
3. Discounting ($\gamma <1$): Ensures finite sums and convergence (contraction).

3. Model-Based vs. Model-Free Learning

3.1 Policy Iteration (Model-Based)

If we know the transition dynamics $p(s^{\prime }|s,a)$, we can use Dynamic Programming.

1. Evaluate: Compute $V^{\pi }(s)$ for current $\pi$.
2. Improve: Update $\pi (s)\leftarrow \arg {\max }_a{E}_{s^{\prime }}[r+\gamma V^{\pi }(s^{\prime })]$.

Limitation: The "Improve" step requires calculating an expectation over $s^{\prime }$. This requires a model ($p$).

3.2 The Q-Function Breakthrough (Model-Free)

Why do we learn $Q(s,a)$ instead of just $V(s)$?

• V-Function: To extract a policy from $V(s)$, we need a model to predict which action leads to the best next state:

• Q-Function: If we have $Q(s,a)$, the "future" and "model" are already baked into the value. We simply pick the biggest number:

Conclusion: Learning $Q$ allows Model-Free control.

4. Fitted Q-Iteration (FQI)

When state spaces are large (e.g., images), we cannot use tables. We must use Function Approximation (Neural Networks) to estimate $Q_{\varphi }(s,a)\approx Q^{\ast }(s,a)$.

4.1 The Algorithm

We solve the Bellman Optimality Equation by turning it into a regression problem.

4.2 Why Regression Works (Stochastic Targets)

The target $y_i$ uses a single sample next state $s_i^{\prime }$, but the Bellman equation requires an expectation $E_{s^{\prime }}$.

• Target: $y_i\approx \text{Sample of }(r+\gamma \max Q)$
• Regression: Minimizing MSE approximates the conditional expectation:

Thus, training on noisy samples allows the network to recover the true expected Bellman update.

4.3 Q-Learning (Online)

Q-Learning is simply the online version of FQI with a batch size of 1.

(Note: We treat $y$ as a fixed constant during the gradient step, even though it depends on $\varphi$.)

5. Theoretical Properties

5.1 Optimality of the Greedy Policy

Does maximizing $Q^{\ast }$ really give the best policy? Yes.

• Definition: $V^{\ast }(s)$ is the maximum possible value achievable by any policy.
• Connection: The policy ${\pi }^{\ast }$ that achieves this maximum satisfies $V^{{\pi }^{\ast }}=V^{\ast }$.
• Result: The Q-function for this policy is $Q^{{\pi }^{\ast }}(s,a)=r+\gamma E[V^{\ast }(s^{\prime })]$, which is exactly the definition of $Q^{\ast }$. Therefore, finding $Q^{\ast }$ is equivalent to finding the optimal policy.

5.2 Convergence Issues

• Tabular Case: The Bellman Operator $\mathcal{B}$ is a contraction in the max-norm ($L_{\infty }$). Iterating it guarantees convergence to $Q^{\ast }$.
• Function Approximation: We cannot represent $Q$ perfectly. Each step involves a "Projection" $\Pi$ (fitting the neural net).
  • $\mathcal{B}$ contracts in $L_{\infty }$.
  • $\Pi$ contracts in $L_2$ (MSE).
  • The Problem: The combination $\Pi \mathcal{B}$ is not necessarily a contraction.
  • Consequence: FQI and Q-Learning can diverge with neural networks (unlike Gradient Bandit or tabular methods).

5.3 Practical Reality: All States vs. Expectation

• Theory (Tabular): We seek Pointwise Optimality ($V^{{\pi }^{\ast }}(s)\ge V^{\pi }(s)$ for all $s$).
• Practice (Deep RL): We minimize error weighted by the data distribution $\rho$.

We maximize performance on average over the states we actually visit, potentially sacrificing accuracy in rare states.