A nonconvex objective that still behaves
The policy gradient theorem gives an unbiased gradient of expected return with respect to policy parameters, so you can do gradient ascent. But expected return is nonconvex in those parameters, and standard optimization theory only promises convergence to a stationary point, not the global optimum. For years it was unclear whether REINFORCE-style methods could be trusted to find the best policy at all.
The policy gradient theorem gives an unbiased gradient of expected return, so you can ascend it even though J is nonconvex.
Why policy gradient reaches the global optimum
Policy gradient convergence theory rests on a gradient domination (a Polyak–Łojasiewicz-type) inequality: the suboptimality of a policy is bounded by the size of its gradient, so a small gradient forces near-optimality rather than allowing a bad flat region. The policy improvement theorem supplies the underlying monotonic-improvement intuition. The catch is the distribution mismatch term: convergence speed depends on how well the states you visit cover the states the optimal policy needs — exploration sneaks back in through the back door.
Interactive ball rolling down a curved loss surface toward its minimum.
Preconditioning the gradient by the Fisher information gives the natural policy gradient, whose convergence is markedly faster and far less sensitive to parameterisation — the theoretical heart of why trust-region methods like TRPO and PPO are so robust in practice.
The average-reward setting
Discounting is a modelling convenience; many real systems — queueing, inventory, ongoing control — genuinely care about long-run throughput. The average-reward criterion optimises reward per step in the limit, with no γ. Its theory replaces the discounted Bellman equation with an average-reward one involving a gain and a bias function, and the 1/(1−γ) factors are replaced by the MDP's mixing time or diameter. Policy-gradient and regret results both have average-reward analogues, though they are technically harder and a frequent source of open problems.
Interactive Markov chain with states, transition arrows, and a settling stationary distribution.
Assembling a PAC guarantee
A full PAC-RL result is a stack of the pieces from this track. You bound per-step model or value error with concentration; you push that error into policy value with the simulation lemma and the approximation error bounds; you control exploration with optimism and a structural measure like Bellman rank; and you certify the optimization step with policy-gradient convergence. The product is an explicit sample complexity: with probability 1−δ, this many samples yield an ε-optimal policy.
The PAC-RL guarantee assembled from the track's pieces: with probability at least 1−δ the returned policy is within ε of optimal, on a sample budget polynomial in the problem parameters.
- Estimate: bound statistical error of model/value via concentration.
- Propagate: convert that error into policy suboptimality (simulation lemma + horizon).
- Explore: cover the needed states with optimism, paying a structure-dependent cost.
- Optimize: drive the policy to ε of optimal with a convergent update.
What is still open
Theory still trails practice. We lack tight sample-complexity bounds for deep nonlinear function approximation; minimax lower bounds for general policy-gradient and average-reward settings remain partly open; offline RL, multi-agent equilibria, and exploration under rich observations all have gaps between what we can do and what we can prove. The healthiest stance is honest: theory tells you which assumptions buy which guarantees, and that map — not a single grand theorem — is what lets you reason about whether an RL method will work before you spend the compute.