Near-optimal Policy Identification in Active Reinforcement Learning

Xiang Li, Viraj Mehta, Johannes Kirschner, Ian Char, Willie Neiswanger, Jeff Schneider, Andreas Krause, Ilija Bogunovic

TL;DR

The paper introduces AE-LSVI, a novel reinforcement learning algorithm designed to find near-optimal policies using a simulator (generative model). By combining optimistic action selection with pessimistic policy estimation, the algorithm provably identifies a robust policy that performs well across the entire state space, achieving sample complexity guarantees that are independent of the total number of states.

What Problem Does This Paper Address?

Most reinforcement learning (RL) algorithms are designed to maximize rewards starting from a specific initial state distribution. However, in real-world applications like robotics or autonomous driving, an agent might encounter states it didn't see during training due to human intervention or environmental shifts.

The authors tackle the challenge of best-policy identification in large state spaces where data acquisition is expensive. They assume the learner has access to a "generative model"—essentially a simulator where you can plug in any state-action pair and see the resulting next state. The goal is to use this simulator efficiently to find a policy that is "uniformly" near-optimal, meaning it works reliably no matter where the agent starts.

Methods

The authors propose Active Exploration with Least-Squares Value Iteration (AE-LSVI). The algorithm operates in the kernelized setting, using Reproducing Kernel Hilbert Space (RKHS) functions to approximate the reward and Q-functions.

Key components include:

  • Kernelized Ridge Regression: Used to estimate the value functions based on collected transitions.
  • Dual Confidence Bounds: The algorithm maintains both optimistic ($ \overline{Q} $) and pessimistic ($ \underline{Q} $) estimates of the optimal Q-function.
  • Active Sampling Rule: Instead of following a trajectory, the algorithm actively queries the simulator at state-action pairs where the gap between the optimistic and pessimistic estimates is largest. Specifically, it targets states where the "best action" is most uncertain.
  • Pessimistic Reporting: When it's time to output the final policy, the algorithm chooses the one that maximizes the lower confidence bound, ensuring robustness.
The AE-LSVI algorithm uses a nested loop structure to iteratively refine value function estimates through active sampling.

Datasets

The researchers evaluated AE-LSVI across two main categories of benchmarks:

  1. Reinforcement Learning Environments:
    • Cartpole swing-up: A classic control task with dense rewards.
  2. 2D Navigation: A task requiring an agent to reach a goal in a coordinate plane.
  3. Plasma Control ($\beta$ Tracking and $\beta$ + Rotation): Complex simulators for nuclear fusion reactors where the goal is to stabilize plasma pressure and rotation.
  4. Contextual Bayesian Optimization (BO) Tasks: Synthetic problems including Branin 1-1, Hartmann 2-2, Hartmann 3-1, and Hartmann 4-2, which serve as proxies for high-dimensional optimization under different contexts.

Key Insights and Ideas

  • Uniformity is Key: Unlike standard RL which minimizes "regret" along a path, AE-LSVI minimizes the $\ell_\infty$ error over the whole state space. This makes the resulting policy much more robust to "out-of-distribution" starting states.
  • Breaking the Curse of Dimensionality: By using kernel methods, the algorithm's sample complexity depends on the "information gain" of the kernel rather than the raw number of states or actions. This allows it to handle continuous or very large discrete spaces.
  • Optimism vs. Pessimism: The "aha moment" here is using optimism to drive exploration (finding what might be good) but using pessimism for the final policy identification (ensuring we only rely on what we know is good).
  • BO Improvement: The authors show that their RL-focused approach, when simplified to the Contextual BO setting, actually yields better theoretical bounds than previous state-of-the-art BO algorithms.

Key Results

In experiments where the agent was tested on an initial state distribution ($p'_0$) different from the one used by standard online algorithms, AE-LSVI significantly outperformed the baselines.

As shown in the table below, while online methods like LSVI-UCB or DDQN perform well when the test distribution matches the training distribution (Table 1 in the paper), they struggle when the starting point is shifted. AE-LSVI maintains high performance, demonstrating its robustness.

Table 2: Average Return showing AE-LSVI outperforming online RL methods when evaluated on a shifted initial state distribution.

Quantitatively, the authors proved that AE-LSVI finds an $\epsilon$-optimal policy with a number of samples that scales polynomially with the horizon $H$ and the kernel's information gain $\Gamma_k$, providing a solid theoretical foundation for its efficiency.

Limitations and Future Work

  • Generative Model Requirement: The algorithm relies on the ability to query the simulator at any state. In many real-world scenarios, you can only reach new states by taking actions from your current one (the "local access" model).
  • Computational Complexity: Like most kernel-based methods, the computational cost of calculating the uncertainty ($\sigma$) scales with the number of samples, which can become a bottleneck for very long training runs.
  • Future Directions: The authors suggest extending this framework to the local access model and exploring more principled ways to choose the exploration parameter $\beta$, which was fixed at 0.5 for their experiments.

Summary updated

Abstract

Many real-world reinforcement learning tasks require control of complex dynamical systems that involve both costly data acquisition processes and large state spaces. In cases where the transition dynamics can be readily evaluated at specified states (e.g., via a simulator), agents can operate in what is often referred to as planning with a \emph{generative model}. We propose the AE-LSVI algorithm for best-policy identification, a novel variant of the kernelized least-squares value iteration (LSVI) algorithm that combines optimism with pessimism for active exploration (AE). AE-LSVI provably identifies a near-optimal policy \emph{uniformly} over an entire state space and achieves polynomial sample complexity guarantees that are independent of the number of states. When specialized to the recently introduced offline contextual Bayesian optimization setting, our algorithm achieves improved sample complexity bounds. Experimentally, we demonstrate that AE-LSVI outperforms other RL algorithms in a variety of environments when robustness to the initial state is required.
BibTeX
@inproceedings{li2023near,
  author = {Xiang Li and Viraj Mehta and Johannes Kirschner and Ian Char and Willie Neiswanger and Jeff Schneider and Andreas Krause and Ilija Bogunovic},
  title = {{Near-optimal Policy Identification in Active Reinforcement Learning}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=3OR2tbtnYC-},
}
Figure