Reinforcement Learning in POMDP's via Direct Gradient Ascent

AI summary

Overview

Research area: Reinforcement learning, specifically policy-gradient methods for Partially Observable Markov Decision Processes (POMDPs).

Technical level: Advanced. The paper is built around four theorems, a bias/variance analysis, and convergence proofs, and it assumes familiarity with Markov chains, stationary distributions, mixing times, and conjugate-gradient optimization.

One-sentence scope: A theoretical and experimental study of GPOMDP, an algorithm that estimates an approximation to the gradient of average reward from a single sample path of a POMDP, together with CONJPOMDP (CONJGRAD), a conjugate-gradient procedure that uses those estimates to search for local optima of the average reward.

What This Paper Is About

The paper addresses the problem that approximate value-function methods in reinforcement learning minimize an error (such as the maximum norm between an approximate value function and the optimal one) that does not guarantee good performance from the resulting greedy policy. The authors instead optimize policy performance directly: they treat the average reward as a differentiable function of policy parameters and search for parameters that maximize it, working in the POMDP framework where both state transitions and the agent's observations are uncertain.

Key Contributions

1. GPOMDP: a REINFORCE-like algorithm for estimating ∇_β η(θ), an approximation to the true gradient ∇η(θ) of average reward with respect to policy parameters, from a single sample path of the underlying Markov chain. It requires storage of only 2K real numbers (K being the number of policy parameters), needs no knowledge of the underlying state, and uses only one free parameter, β ∈ [0, 1), which has a natural interpretation as a bias-variance trade-off.

2. Convergence and finite-time guarantees: a proof that the GPOMDP estimate Δ_t converges to ∇_β η with probability 1 (Theorem 4) under Assumptions 1 and 2, plus a characterization of finite-time behavior stating that if t > Ω(τ*(θ) / (ε²(1−β)²)), then ||Δ_t − ∇β η(θ)||∞ < ε with high probability.

3. A gradient decomposition with a bias bound: Theorem 1 splits ∇η into (1−β)∇π′J_β + βπ′∇PJ_β; Theorem 2 shows ∇η = lim_{β→1} ∇_β η; Theorem 3 bounds the approximation error by C τ*(θ)(1−β), where C = C(B, R, n) is a universal constant, B bounds |∇μ/μ|, R bounds the rewards, n is the number of states, and τ*(θ) is the mixing time.

4. CONJPOMDP (CONJGRAD): a Polak-Ribiere-style conjugate-gradient optimization procedure that operates on noisy (and possibly biased) gradient estimates, using a line search (GSEARCH) that brackets the maximum using gradient information rather than value estimates.

Main Findings

• Gradient approximation is controlled by β relative to mixing time. Theorem 3 shows the error between ∇η(θ) and ∇_β η(θ) is at most C τ*(θ)(1−β). When 1/(1−β) is large compared with the mixing time τ*(θ), ∇β η(θ) approximates ∇η(θ) well, and lim{β→1} ∇_β η(θ) = ∇η(θ).

• Explicit bias-variance trade-off in β. Equation (9) says β must be close to 1 to reduce bias; Equation (11) says β should be as close to 0 as possible to reduce the variance of GPOMDP's estimates at time t. GPOMDP therefore depends on one parameter with a clear interpretation.

• Running time is bounded by mixing time, not recurrence time. The paper argues that policy-gradient algorithms with proven convergence all rely on an identifiable recurrent state, and that as state spaces grow, the expected time between visits to that state grows and depends on the policy parameters. GPOMDP's running time is instead bounded by the mixing time, "which is always shorter than recurrence time and often substantially so."

• Convergence with probability 1. Under Assumption 1 (unique stationary distribution π(θ), rewards bounded by R < ∞) and Assumption 2 (the derivatives ∂μ_u(θ,y)/∂θ_k exist and the ratios |∂μ_u/∂θ_k| / μ_u(θ,y) are uniformly bounded by B < ∞), Algorithm 1 starting from any initial state i₀ produces Δ₀, Δ₁, … with lim_{t→∞} Δ_t = ∇_β η w.p.1.

• Line search bracketing is more robust with gradient information. GSEARCH finds two points in a search direction with GRAD(θ₁)·θ* > 0 and GRAD(θ₂)·θ* < 0. The paper notes that the variance of sign[GRAD(θ₁)·θ*] is independent of the distance between θ₁ and θ₂, whereas the variance of comparing function values increases as the points get closer together. The stated disadvantage is that extreme overshooting cannot be detected using gradient estimates alone.

• Experiment: three-state MDP. In a three-state MDP with two actions per state, relative errors ||Δ_T − ∇η||/||∇η|| show that larger β increases GPOMDP's variance (Figure 1) while producing a corresponding decrease in final bias (Figure 2), illustrating the trade-off.

• Experiment: CONJPOMDP training. With β set to 0, s₀ = 100, and ε = 0.0001, CONJPOMDP converged to near-optimality. Results were averaged over 500 independent runs with controller parameters randomly initialized in the range [−0.1, 0.1]. The average reward of the optimal policy is 0.8; the paper reports that the extremely large initial step size s₀ "considerably reduced the time required for the controller to converge to near-optimality," and that none of the values were critical.

• TD(1) contrast. The paper's chosen feature vectors ((12/18, 6/18), (6/18, 12/18), (5/18, 5/18) for states A, B, C) ensure that a value function linear in those features and trained with TD(1) while observing the optimal policy will itself implement a suboptimal one-step greedy lookahead policy, so in this system TD(1) is guaranteed to produce a worse policy if it starts out observing the optimal policy. The optimal policy is to always select action a₂.

• Not reported. All proofs are omitted due to space constraints, and the paper states that more realistic experiments are discussed elsewhere rather than in this paper. Precise statements of the finite-time bound and the full experimental details of the "closer to reality" experiments are also not given here.

Methodology in Plain English

The authors set up a finite POMDP with n states, N controls, and M observations, where each state carries a reward r(i), each control u determines a stochastic transition matrix P(u) = [p_ij(u)], and each state generates an observation y with probability ν_y(i). A randomized policy μ maps observations to distributions over controls, and is parameterized by θ ∈ ℝ^K, giving a Markov chain with transition matrix P(θ) and stationary distribution π(θ). The objective is η(θ) = π′(θ)r, the long-term average reward.

They first write the exact gradient as ∇η = π′∇P[I − P + eπ′]⁻¹ r, and note this requires knowing transition and observation probabilities and inverting a matrix, so it is intractable for most practical problems. They then show the gradient can be split into two parts, one of which vanishes as a discount factor β goes to 1, yielding the approximate gradient ∇_β η := π′∇PJ_β.

To estimate that quantity, GPOMDP maintains two vectors z_t and Δ_t (each in ℝ^K, initialized to zero). After each observed action and subsequent reward, it updates z_{t+1} = βz_t + ∇μ_{u_t}(θ,y_t)/μ_{u_t}(θ,y_t) and then Δ_{t+1} = Δ_t + (1/(t+1))[r(i_{t+1})z_{t+1} − Δ_t], which is a running average of r(i_t)z_t. The Δ_t estimate converges to ∇_β η.

For optimization, CONJPOMDP repeatedly calls GPOMDP to get a gradient estimate, uses it to pick an uphill direction, and calls GSEARCH to find a local maximum along that direction. GSEARCH brackets the maximum by stepping forward or backward (doubling or halving the step size) until the directional gradient changes sign, then uses quadratic interpolation on the bracketing points' gradient projections to jump to the maximum. A step-size update γ = (Δ − g)·Δ/||g||² follows the Polak-Ribiere conjugate-gradient pattern, and CONJPOMDP terminates when ||GRAD(θ)||² falls below ε.

Why This Matters

Impact on research. The paper argues that value-function approaches suffer a fundamental limitation: even accurate approximations to the optimal value function can generate bad greedy policies when the discount factor is close to 1 (the bound given is η = η* − 2αε/(1−α)). It reframes the goal as directly searching for a policy that maximizes expected reward, and it introduces a gradient estimator whose running time depends on the mixing time of the underlying chain rather than on the recurrence time of an identifiable state. It also questions the "folklore" belief that gradient-based methods suffer from unacceptably large variance, calling the reasons for that conclusion unclear and warranting further investigation.

Real-world applications (domains the paper cites as prior reinforcement learning successes):

• Game playing, including checkers, backgammon, and chess.
• Job-shop scheduling.
• Dynamic channel allocation.
• Any control problem where the agent must act on observations rather than on the underlying state — the POMDP setting the paper formalizes.

Industry relevance. Because GPOMDP requires no knowledge of the underlying state, stores only 2K real numbers, and learns from a single sample path, it is suited to settings where the state is hidden or hard to estimate and where transition and observation probabilities are unknown. The paper also frames direct policy search as often easier than value-function design, since "we often know how to act without being able to compute the value of acting."

Future Directions

• Automatic parameter selection. The authors identify as a weakness the need to specify running times and the discount factor β in advance, and state they are currently investigating automatic algorithms for finding these variables.
• Explaining the variance folklore. The paper calls for further investigation into why gradient-based methods are widely believed to suffer from unacceptably large variance.
• Multi-agent settings. Generalizing GPOMDP to multi-agent settings is described as "particularly exciting."
• Biological learning. The authors raise implications for learning in biological neural networks.
• Exact solution for small POMDPs. The paper notes that for POMDPs with sufficiently few states and known transition and observation probabilities, Equation (4) could be solved exactly to give the precise gradient direction, which it calls an interesting avenue for further investigation, while noting POMDPs are generally intractable even for small numbers of states.
• Memory-based policies. Policies with memory, such as parameterized finite automata, are noted as the subject of ongoing research and beyond the scope of this paper.

Target Audience

This paper benefits most readers who already have a grounding in Markov decision processes, stochastic approximation, and optimization — graduate students and researchers in reinforcement learning, control theory, and operations research who want a theoretically grounded alternative to approximate value-function methods. It is also relevant to practitioners working on partially observable control problems where the state is hidden and transition probabilities are unknown, and who need an algorithm with a convergence guarantee and a single tunable bias-variance parameter. Readers looking for empirical benchmarks or large-scale experiments will not find them here; the paper contains one "toy" three-state experiment and omits all proofs due to space constraints.

Authors’ abstract

This paper discusses theoretical and experimental aspects of gradient-based approaches to the direct optimization of policy performance in controlled POMDPs. We introduce GPOMDP, a REINFORCE-like algorithm for estimating an approximation to the gradient of the average reward as a function of the parameters of a stochastic policy. The algorithm's chief advantages are that it requires only a single sample path of the underlying Markov chain, it uses only one free parameter $β\in [0,1)$, which has a natural interpretation in terms of bias-variance trade-off, and it requires no knowledge of the underlying state. We prove convergence of GPOMDP and show how the gradient estimates produced by GPOMDP can be used in a conjugate-gradient procedure to find local optima of the average reward.