Policy Optimization via Importance Sampling

Alberto Maria Metelli, Matteo Papini, Francesco Faccio, Marcello Restelli

Overview

The researchers introduce POIS (Policy Optimization via Importance Sampling), a novel reinforcement learning (RL) algorithm that reuses trajectory data more efficiently by optimizing a "variance-aware" surrogate objective. By deriving high-confidence bounds based on Rényi divergence, POIS explicitly accounts for the uncertainty introduced by importance sampling. This allows for aggressive offline optimization without the risk of "over-optimizing" on stale data.

The Challenge of Data Reuse in RL

In Reinforcement Learning, data collection is expensive. "On-policy" methods like REINFORCE are statistically "safe" but wasteful, often discarding a batch of trajectories after a single gradient update. Conversely, "off-policy" methods attempt to reuse old data (the "behavioral policy") to improve a new "target policy" using Importance Sampling (IS).

However, IS is a double-edged sword. If the target policy drifts too far from the behavioral policy, the variance of the performance estimate explodes, leading to unstable updates. While popular algorithms like TRPO and PPO use heuristics—such as KL-divergence constraints or clipping—to keep updates small, they do not explicitly model the statistical uncertainty inherent in the IS estimator itself. The authors ask: How can we maximize data reuse while mathematically guaranteeing we aren't being misled by high-variance estimates?

The POIS Algorithm

The core contribution is the POIS algorithm, which is introduced in two flavors: Action-based (A-POIS) and Parameter-based (P-POIS).

  1. Surrogate Objective: Instead of maximizing the estimated return directly, POIS maximizes a statistical lower bound. This objective consists of the importance-sampled return minus a penalty term that represents the uncertainty.
  2. Rényi Divergence ($d_2$): To quantify the "distance" between policies and the resulting variance, the authors use the 2-Rényi divergence. They prove that the variance of the IS estimator is bounded by this divergence.
  3. High-Confidence Bounds: Using Chebyshev-like inequalities (specifically Cantelli’s inequality), they derive a bound that holds with probability $1-\delta$. This $\delta$ parameter allows practitioners to tune how "risk-averse" the algorithm should be.
  4. Natural Gradients: To navigate the policy parameter space efficiently, the authors employ natural gradients, showing a tight connection between the geometry of the Rényi divergence and the Fisher Information Matrix (FIM).
  5. Neuron-Based POIS (N-POIS): For deep neural networks, where the parameter space is massive, the authors suggest grouping weights by neuron to calculate independent importance weights, mitigating the "curse of dimensionality" that usually plagues parameter-based methods.

Core Insights

  • Variance as a First-Class Citizen: Most RL algorithms treat variance as a nuisance to be reduced. POIS treats it as a fundamental constraint on how much we can learn from a specific batch of data.
  • The "Trust Region" is Emergent: In TRPO, the trust region (the KL constraint) is a hard requirement chosen by the user. In POIS, the "safe zone" for optimization emerges naturally from the trade-off between the estimated gain and the $d_2$-based penalty in the objective function.
  • Parameter-based Advantage: The authors found that P-POIS (searching in the space of policy weights rather than actions) often outperforms action-based methods on simpler tasks. This is because P-POIS importance weights are based on the hyperpolicy distribution, which doesn't suffer from the "product-over-time-steps" variance explosion seen in trajectory-level IS.

Performance and Results

The algorithm was evaluated on several classic continuous control benchmarks from the rllab and OpenAI Gym ecosystems, including Cartpole Balancing, Mountain Car, Inverted Pendulum, Inverted Double Pendulum, Acrobot, and Swimmer.

Performance comparison of POIS variants against TRPO and PPO across continuous control tasks.
  • Superiority in Linear Policies: On tasks with linear policies (like Cartpole and Inverted Double Pendulum), P-POIS significantly outperformed both TRPO and PPO, achieving higher returns with fewer trajectories.
  • Competitive Deep Learning: When scaled to deep neural networks, A-POIS achieved performance comparable to or better than TRPO and DDPG. For instance, on the "Cart-Pole Balancing" task with deep policies, A-POIS reached a return of ~4842, rivaling TRPO's ~4869 but with tighter confidence intervals.
  • Sensitivity to $\delta$: The experiments confirmed that the confidence parameter $\delta$ effectively controls the algorithm's behavior. A small $\delta$ leads to conservative, steady improvements, while a larger $\delta$ allows for faster but riskier convergence.

Limitations and Future Directions

  • Trajectory-Level Credit Assignment: POIS currently operates at the trajectory level. This means it cannot distinguish between a "good" sequence of actions inside a "bad" overall trajectory. The authors suggest that per-decision importance sampling could be a promising way to provide finer-grained credit assignment.
  • Curse of Dimensionality in P-POIS: While the "Neuron-Based" trick helps, P-POIS still struggles with extremely high-dimensional parameter spaces (very deep/wide networks) because the importance weights can easily collapse to zero.
  • Stochastic Environments: The current Rényi divergence estimation for A-POIS requires an approximation that might be too conservative in highly stochastic environments. Future work could focus on more efficient ways to estimate these divergences without needing a perfect model of the environment's transitions.

Summary updated

Abstract

Policy optimization is an effective reinforcement learning approach to solve continuous control tasks. Recent achievements have shown that alternating online and offline optimization is a successful choice for efficient trajectory reuse. However, deciding when to stop optimizing and collect new trajectories is non-trivial, as it requires to account for the variance of the objective function estimate. In this paper, we propose a novel, model-free, policy search algorithm, POIS, applicable in both action-based and parameter-based settings. We first derive a high-confidence bound for importance sampling estimation; then we define a surrogate objective function, which is optimized offline whenever a new batch of trajectories is collected. Finally, the algorithm is tested on a selection of continuous control tasks, with both linear and deep policies, and compared with state-of-the-art policy optimization methods.
BibTeX
@inproceedings{metelli2018policy,
  author = {Alberto Maria Metelli and Matteo Papini and Francesco Faccio and Marcello Restelli},
  title = {{Policy Optimization via Importance Sampling}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=HkZJ1Kb_ZB},
}
Figure