Optimistic Planning over Confidence Sets of Transition Models

149 concepts129 papers2 proposals

In reinforcement learning (RL), the exploration-exploitation dilemma is traditionally solved by being "optimistic in the face of uncertainty." In model-free RL, this principle usually manifests as adding an exploration bonus directly to estimated state-action values (such as in Upper Confidence Bound algorithms). However, in complex, structured, or continuous environments, model-free exploration can be highly inefficient because it treats every state transition as an isolated surprise, failing to leverage the underlying physics or transition dynamics of the system.

An alternative, highly sample-efficient paradigm is optimistic model-based planning. Instead of being optimistic about the value of an action, the agent maintains a confidence set of plausible transition models that are statistically consistent with historical data. It then selects the single model within this set that yields the highest potential reward and plans its policy against that model.

The Core Intuition: The Win-Win Loop

Why does planning against the most optimistic plausible model work? It creates an elegant "win-win" guarantee for the agent's trajectory:

  1. The Win (Exploitation): If the chosen optimistic model happens to be close to the true environment dynamics, the planned policy will achieve high rewards in reality.
  2. The Learning (Exploration): If the optimistic model is wildly incorrect, the agent will execute actions expecting high rewards, but the actual environment transitions will deviate significantly from the model's predictions. This new data will immediately invalidate the incorrect model, shrinking the confidence set and preventing the agent from making the same mistake again.

This mechanism ensures that the agent strategically explores precisely where its model uncertainty allows for high potential payoffs, leading to provably low regret (often scaling with $O(\sqrt{T})$).

  [ Historical Data ]
          │
          ▼
┌────────────────────────────────────────┐
│ Construct Confidence Set of Models (ℳ) │
└────────────────────────────────────────┘
          │
          ▼
┌────────────────────────────────────────┐
│  Select Most Optimistic Model M ∈ ℳ   │
└────────────────────────────────────────┘
          │
          ▼
┌────────────────────────────────────────┐
│   Plan & Execute Optimal Policy for M  │
└────────────────────────────────────────┘
          │
          ▼
   [ New Transition ] ───► (Shrinks ℳ if model was wrong)

Constructing Confidence Sets Across Environments

The shape and mathematical formulation of the confidence set depend heavily on the structure of the environment. Researchers have tailored this framework to various settings:

  • Linear-Quadratic Regulators (LQR) and Linear Systems: For continuous linear systems, the confidence set is typically a confidence ellipsoid centered around least-squares parameter estimates. Abbasi-Yadkori et al. and Cohen et al. demonstrated how maintaining these ellipsoids allows for efficient adaptive control with optimal regret bounds. Javanmard et al. extended this to high-dimensional systems by incorporating sparsity constraints (like LASSO) into the confidence set construction, breaking the curse of dimensionality.
  • General and Non-Linear Dynamics: When transitions belong to more complex families, such as linearly parameterized exponential families, Gopalan et al. showed that confidence sets can be constructed around penalized maximum likelihood estimates. To avoid the computational bottlenecks of maximum likelihood in non-linear settings, Li et al. proposed using score matching to construct closed-form confidence ellipsoids efficiently.
  • Partially Observable Environments (POMDPs): In systems where the true state is hidden, building confidence sets is notoriously difficult. Early approaches by Azizzadenesheli et al. used spectral tensor decomposition to consistently estimate hidden structures and form confidence intervals. More recently, Liu et al. introduced Optimistic Maximum Likelihood Estimation (OMLE), which unifies model estimation and exploration by maintaining a confidence set of models consistent with observed histories, proving that even "overcomplete" POMDPs can be solved sample-efficiently.

The Planning Challenge: Solving the Optimistic Oracle

Once a confidence set of models $\mathcal{M}$ is established, the agent faces a joint optimization problem: find both the model $M$ within the confidence set $\mathcal{M}$ and the policy $\pi$ that maximize the expected reward:

$$\max_{M \in \mathcal{M}, \pi} V^\pi_M$$

Solving this exactly can be computationally demanding, as it requires searching over an uncountably infinite set of models. Different frameworks employ distinct algorithmic oracles to handle this:

  • Convex Relaxations: In LQR settings, Cohen et al. reformulated this joint optimization as a convex semi-definite program (SDP), making the optimistic selection computationally efficient.
  • Occupancy Measures: For adversarial or changing reward settings, Rosenberg et al. optimized over occupancy measures subject to transition constraints within the confidence set, bypassing the need to explicitly instantiate the optimal model.
  • Hypothesis Selection: Hu et al. proposed a unified objective function ("Maximize to Explore") that fuses estimation and planning by directly searching for hypotheses that maximize predicted total rewards while penalizing those inconsistent with historical data.

Broader Horizons: Safety, Multi-Agent, and Bandits

The principle of optimistic model selection extends far beyond standard Markov Decision Processes:

  • Constrained and Safe RL: In environments with safety constraints, HasanzadeZonuzy et al. showed that solving an optimistic optimization problem over a confidence interval ensures the agent finds a feasible, safe policy as long as the true dynamics reside within the confidence set.
  • Multi-Agent Systems: Sessa et al. brought this concept to general-sum games by computing equilibria on "hallucinated" models within the confidence bounds, ensuring efficient multi-agent exploration.
  • Model Selection in Bandits: Even in contextual bandits or model zoos, Turan and Hu et al. demonstrated that constructing confidence sets over candidate models allows an agent to adaptively select the best model for a given context or prompt.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_optimistic_model_selection_c9a11917,
  title = {optimistic model selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimistic-model-selection/rdr_c9a11917e4db446eb3dac10d7639bfde},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_optimistic_model_selection_c9a11917_v1,
  title = {optimistic model selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimistic-model-selection/rdr_c9a11917e4db446eb3dac10d7639bfde/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake