Actor-Critic Methods

A reinforcement learning agent seeks a policy $\pi_\theta(a\mid s)$ that maximizes the expected discounted return $J(\theta) = \mathbb{E}_{\pi_\theta}\left[\sum_{t=0}^{\infty}\gamma^t r_t\right]$. The policy gradient theorem states

REINFORCE estimates $Q^{\pi_\theta}(s_t,a_t)$ with the empirical Monte Carlo return $G_t = \sum_{k\ge t}\gamma^{k-t} r_k$, an unbiased but extremely high-variance estimator (every future random reward contributes noise). Baselines and Variance Reduction shows that subtracting any state-dependent baseline $b(s_t)$ leaves the gradient unbiased while shrinking its variance; the best baseline is close to $V^{\pi_\theta}(s_t)$. An actor-critic method takes this one step further: instead of only subtracting a learned baseline from the Monte Carlo return, it replaces the Monte Carlo return itself with a bootstrapped estimate. The critic is a function approximator $V_w(s)$ (or $Q_w(s,a)$) trained by TD learning to approximate the true value function. The actor is the policy $\pi_\theta$, updated in the direction that increases the log-probability of actions the critic judges better than expected. The signal used is the TD error,

which is an unbiased estimator of the advantage $A^{\pi}(s_t,a_t) = Q^{\pi}(s_t,a_t) - V^{\pi}(s_t)$ when $V_w = V^\pi$ exactly. In practice $V_w$ is only approximate, so $\delta_t$ is a biased but low-variance advantage estimate — the central bias-variance tradeoff of the whole family. This is the direct predecessor of The Advantage Function as a formal object, and of Generalized Advantage Estimation, which interpolates between the one-step $\delta_t$ used here and the full Monte Carlo return.

The mechanism has two coupled update loops running at every timestep: the critic minimizes TD error via semi-gradient descent, and the actor performs gradient ascent on log-probability weighted by that same TD error.

Step by step, for the classic one-step (online) actor-critic: 1. Observe state $s_t$; sample action $a_t \sim \pi_\theta(\cdot \mid s_t)$. 2. Execute $a_t$; observe reward $r_t$ and next state $s_{t+1}$. 3. Compute the TD error: $\delta_t = r_t + \gamma V_w(s_{t+1}) - V_w(s_t)$ (use $\delta_t = r_t - V_w(s_t)$ if $s_{t+1}$ is terminal). 4. Update the critic: $w \leftarrow w + \alpha_w\, \delta_t\, \nabla_w V_w(s_t)$. 5. Update the actor: $\theta \leftarrow \theta + \alpha_\theta\, \gamma^t\, \delta_t\, \nabla_\theta \log \pi_\theta(a_t \mid s_t)$. 6. $s_t \leftarrow s_{t+1}$; repeat until terminal. The $\gamma^t$ term is the discounting-by-time-step required by the exact policy gradient theorem; in practice many implementations drop it (a common, usually benign, approximation that shifts weight toward later-episode transitions but simplifies the algorithm and often improves empirical performance). ``` ActorCritic(env, alpha_theta, alpha_w, gamma, num_episodes): initialize actor parameters theta # policy network pi_theta(a|s) initialize critic parameters w # value network V_w(s) for episode in 1..num_episodes: s = env.reset() I = 1 # running discount factor gamma^t done = False while not done: a ~ pi_theta( . | s) # sample action from current policy s_next, r, done = env.step(a) if done: td_target = r else: td_target = r + gamma * V_w(s_next) delta = td_target - V_w(s) # TD error == 1-step advantage estimate

# critic update: semi-gradient TD(0) on the value function w = w + alpha_w delta grad_w( V_w(s) )

# actor update: policy gradient ascent scaled by the critic's signal theta = theta + alpha_theta I delta grad_theta( log pi_theta(a|s) ) I = gamma I s = s_next return theta, w ``` The corresponding architecture is two networks sharing an environment loop but not (necessarily) parameters, with the critic's scalar error feeding both its own update and the actor's update.

Time complexity per step: $O(f_\theta + f_w)$, where $f_\theta$ and $f_w$ are the costs of one forward/backward pass through the actor and critic networks respectively. With tabular representations this is $O(1)$ per update (a single table entry each). This is the same per-step cost as ordinary TD(0) or a single REINFORCE step evaluated online, and it is asymptotically cheaper per update than Monte Carlo policy gradient, which must wait $O(H)$ steps (episode horizon $H$) before performing any update at all — actor-critic updates continuously and online, which matters enormously for continuing (non-episodic) tasks where $H = \infty$ and Monte Carlo methods cannot even be defined without truncation.

Space complexity: $O(|\theta| + |w|)$ for the two parameter vectors, plus $O(1)$ additional state (no need to store a whole trajectory, unlike REINFORCE with Monte Carlo returns, which needs $O(H)$ storage for rewards if returns are computed by backward accumulation, or can be computed online with a running return but still needs $O(H)$ variance-inducing delay before any usable gradient signal appears).

Correctness argument. Two claims must be justified: that the critic converges to (an approximation of) $V^{\pi_\theta}$, and that the resulting actor update is a valid ascent direction for $J(\theta)$. Critic convergence. The critic update is exactly semi-gradient TD(0):

Under a fixed policy $\pi_\theta$ (i.e., treating $\theta$ as momentarily frozen), for linear function approximation and step sizes satisfying the Robbins–Monro conditions ($\sum \alpha_w = \infty$, $\sum \alpha_w^2 < \infty$), this converges to the TD fixed point $w^*$ satisfying the projected Bellman equation — the standard TD(0) convergence guarantee, exactly as used in Temporal-Difference Learning. In the actor-critic setting $\theta$ moves too, but on a slower timescale in the standard two-timescale analysis ($\alpha_\theta \ll \alpha_w$ asymptotically), so the critic effectively tracks $V^{\pi_\theta}$ as if $\theta$ were quasi-static. This two-timescale stochastic approximation argument (Borkar's framework) is what makes the coupled system provably convergent under standard conditions, even though actor and critic update simultaneously. Actor ascent direction. Substitute $\delta_t$ for $Q^\pi(s_t,a_t)$ in the policy gradient theorem. Write $\delta_t = A^\pi(s_t,a_t) + \epsilon_t$, where $\epsilon_t = V^\pi(s_t) - V_w(s_t) + \gamma\big(V_w(s_{t+1}) - V^\pi(s_{t+1})\big)$ collects the critic's approximation error. If $V_w = V^\pi$ exactly, $\epsilon_t = 0$ and

using the baseline-subtraction identity from Baselines and Variance Reduction (since $\mathbb{E}_{a\sim\pi}[\nabla_\theta\log\pi_\theta(a|s)\, V^\pi(s)] = 0$, subtracting $V^\pi(s)$ never introduces bias). When $V_w \ne V^\pi$, the actor update is biased by $\mathbb{E}[\epsilon_t \nabla_\theta \log\pi_\theta]$, which vanishes only in expectation if the critic error is uncorrelated with the score function — generally not exactly true, but small when the critic is a good approximator. This is the honest tradeoff: actor-critic sacrifices the zero-bias guarantee of REINFORCE for a large variance reduction, and the quality of that trade is entirely governed by critic accuracy.

Variance comparison, informally. REINFORCE's per-step gradient term has variance scaling with $\mathrm{Var}(G_t)$, which accumulates variance from every reward at every future timestep (roughly $O(H)$ independent noisy terms for horizon $H$, so variance can grow linearly or worse in $H$). The TD error $\delta_t$ depends on only one sampled reward and one bootstrapped estimate, so its variance is bounded independent of horizon (assuming bounded rewards and a stable critic) — this is precisely why actor-critic scales to long or infinite-horizon tasks where Monte Carlo REINFORCE becomes unusable.

Consider a tiny 1-D corridor with 3 non-terminal states $\{s_1, s_2, s_3\}$ and a terminal state $s_4$ (goal). At each state the agent chooses "forward" (F) or "back" (B); forward always advances one state and gives reward $-1$ (step cost); reaching $s_4$ ends the episode. Discount $\gamma = 0.9$. Suppose the tabular critic currently holds

and the actor's current policy assigns $\pi_\theta(F\mid s_2) = 0.7$.

Trace one transition: agent is at $s_2$, samples $a = F$, environment returns $r = -1$, next state $s_3$ (non-terminal).

Critic update (step size $\alpha_w = 0.1$, tabular so $\nabla_w V_w(s_2) = 1$ for the $s_2$ entry):

Actor update (step size $\alpha_\theta = 0.05$, softmax policy over $\{F,B\}$; $\nabla_\theta \log \pi_\theta(F\mid s_2) = 1 - \pi_\theta(F\mid s_2) = 0.3$ for the logit of $F$):

Interpretation: the TD error is negative, meaning the actual outcome ($-1$ reward plus a discounted future value of $2.7$) was slightly worse than the critic's prior expectation of $2.0$ for being in $s_2$ — wait, actually $-1+2.7 = 1.7 < 2.0$, so yes, worse than expected — so the actor slightly decreases the log-probability of having chosen F in $s_2$. Both updates move in the direction that corrects the critic's overestimate and discourages the action that led to a below-expectation outcome. Note the asymmetry with REINFORCE: this update happened immediately, using only one reward and one bootstrapped value, without waiting for the episode (which might still take many more steps) to finish.

Contrast with Monte Carlo REINFORCE on the same transition: REINFORCE would need the full return from $s_2$ onward, e.g., if the episode takes 2 more steps to terminate ($s_3 \to s_4$, one more $-1$ reward), the actual return is $G = -1 + \gamma(-1) = -1.9$, and REINFORCE's (baseline-subtracted) update uses $G - b(s_2)$ instead of $\delta$ — available only after the episode ends, and carrying the variance of however many random future rewards occur before termination.

Actor-critic is the architectural backbone of essentially every modern deep reinforcement learning system that must handle continuous or high-dimensional action spaces. A3C/A2C (Asynchronous/synchronous Advantage Actor-Critic) popularized parallel actor-critic training across many environment copies for Atari and simple continuous-control benchmarks. DDPG, TD3, and SAC are actor-critic methods specialized for continuous control (robotics, simulated locomotion), each differing mainly in how the critic is trained and how the deterministic or stochastic actor is regularized. PPO, arguably the most widely deployed policy-optimization algorithm in industry, is an actor-critic method at its core, using a learned value function as a critic to compute advantages via Generalized Advantage Estimation before clipping the actor's update. Beyond simulated control and games, actor-critic ideas underlie RLHF (reinforcement learning from human feedback), the technique used to align large language models: the "actor" is the language-model policy generating tokens, and the "critic" is a learned value model estimating expected downstream reward (often derived from a human-preference reward model), with PPO-style actor-critic updates driving the fine-tuning. Recommendation systems, autonomous driving stacks, resource allocation in data centers, and financial trading agents that use policy optimization typically rely on some actor-critic variant, because it is the only architecture that simultaneously supports arbitrary action spaces, online per-step learning, and (with the right critic design) tractable variance.

Ask the tutor: How does Generalized Advantage Estimation interpolate between the one-step TD error used here and the full Monte Carlo return?