Posterior Value Functions: Hindsight Baselines for Policy Gradient Methods

Chris Nota, Philip S. Thomas, Bruno C. da SilvaICML 2021 · OpenReview

Policy gradient methods are a cornerstone of modern Reinforcement Learning (RL), but they are notoriously "noisy." Because environments and agent policies are often stochastic, the rewards received in a single episode might not accurately reflect the true quality of the actions taken. This paper introduces posterior value functions, a novel class of baselines that leverage "hindsight" to reduce gradient variance. By using information gathered after an action is taken to infer hidden state components, these baselines provide a more accurate evaluation of past actions without introducing bias, leading to more stable and efficient learning.

The Challenge of Delayed Information

To combat noise, RL researchers typically use baselines (like the state-value function $V(s)$) to subtract the "expected" outcome from the actual outcome, leaving only the "advantage" of the specific action. However, standard baselines are restricted: they can only use information available at the time the action was chosen.

Consider a simple commuting scenario:

The traffic analogy illustrates how hidden states (like traffic) can confound standard RL baselines.

If an agent encounters an unavoidable delay—like a traffic jam that was already present but not yet visible when leaving home—a standard RL agent might incorrectly "blame" its earlier, unrelated actions (such as using a turn signal) for the bad outcome. Hindsight addresses this by using future information to clarify past states. It allows the agent to realize the traffic was inevitable, smoothing out the noise caused by hidden variables or random chance that the agent couldn't have influenced anyway.

Posterior Value Functions

To formalize this intuition, the authors propose the Posterior Value Function $u_t^\theta(H)$, defined as the expected value of the state $S_t$ given the entire history of the episode $H$.

Key technical contributions include:

  • Hindsight in POMDPs: In Partially Observable Markov Decision Processes (POMDPs), the agent doesn't know the full state. The posterior value function uses the full episode trajectory to infer what the hidden state components were at time $t$.
  • Stochasticity as Partial Observability: The authors prove a powerful theoretical bridge: any stochastic MDP can be modeled as a POMDP where the "randomness" is actually a hidden state component. This allows hindsight to reduce variance even in fully observable environments by treating random transitions as pre-determined hidden information revealed later.
  • Unbiased Variance Reduction: They mathematically prove (Theorems 1 and 3) that these baselines are unbiased and that they reduce (and never increase) the variance of policy gradient estimators compared to traditional state-value functions.
  • Indistinguishable Models: Theorem 4 shows that an agent doesn't need to learn the "true" model of the world. It only needs a model that is "indistinguishable" from its perspective to gain the benefits of hindsight, making the approach practical for complex environments.

Experimental Validation

The authors evaluate their approach on a custom Tabular Gridworld domain. In this environment, the agent must navigate a grid where the layout (wall configurations and reward locations) is chosen at random at the start of the episode, but remains hidden until explored.

They compared "Reactive" policies (using only current position) and "Belief" policies (using a distribution over possible maps) against Observation-based, Prior-based, and the new Posterior-based value functions.

Results showing returns and variance over episodes. Posterior baselines drastically reduce variance and improve convergence.

The results demonstrate a drastic variance reduction. The posterior value function baselines produced significantly lower variance in advantage estimates compared to both observation-based and prior-based baselines. Furthermore, this stability translated to faster convergence; while the "Belief" policy eventually reached high returns with all baselines, the posterior baseline allowed the simpler "Reactive" policy to achieve much more stable and rapid learning curves.

Limitations and Future Directions

While theoretically sound, computing the posterior requires a "hindsight model." In complex environments, learning this model—essentially performing inference over past states—can be computationally expensive. Additionally, when using neural networks for function approximation, the system might not converge to the exact theoretical optimum unless highly overparameterized.

Future work will likely explore integrating this approach with Variational Inference (VI) to learn approximate hindsight models in high-dimensional spaces, potentially unlocking "free" variance reduction for deep RL agents in highly stochastic environments.

Summary updated

Abstract

Hindsight allows reinforcement learning agents to leverage new observations to make inferences about earlier states and transitions. In this paper, we exploit the idea of hindsight and introduce posterior value functions. Posterior value functions are computed by inferring the posterior distribution over hidden components of the state in previous timesteps and can be used to construct novel unbiased baselines for policy gradient methods. Importantly, we prove that these baselines reduce (and never increase) the variance of policy gradient estimators compared to traditional state value functions. While the posterior value function is motivated by partial observability, we extend these results to arbitrary stochastic MDPs by showing that hindsight-capable agents can model stochasticity in the environment as a special case of partial observability. Finally, we introduce a pair of methods for learning posterior value functions and prove their convergence.
BibTeX
@inproceedings{nota2021posterior,
  author = {Chris Nota and Philip S. Thomas and Bruno C. da Silva},
  title = {{Posterior Value Functions: Hindsight Baselines for Policy Gradient Methods}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=JaM7zJUPjJ},
}
Figure