The "Optimism in the Face of Uncertainty" (OFU) principle is one of the most successful paradigms in theoretical reinforcement learning (RL). By maintaining a confidence set of plausible environments or value functions and choosing the most favorable one, an agent guarantees a powerful win-win scenario: either it achieves high rewards because its optimistic model is accurate, or it suffers a disappointment that provides highly informative data, narrowing its uncertainty. As formalized by Russo et al. through concepts like the Eluder dimension, this mechanism yields near-optimal sample complexity across a wide range of problems.
However, a profound gap exists between statistical sample efficiency and computational tractability. While an optimistic agent needs very little data to learn, finding that "most optimistic" policy or model requires solving a global optimization problem over a complex, non-convex confidence set at every step. In theoretical proofs, this burden is routinely swept under the rug by assuming the existence of an "optimistic planning oracle." In practice, this oracle is frequently NP-hard, creating a severe computational bottleneck that prevents these algorithms from scaling beyond simple tabular settings.
Why Optimism is Computationally Hard
To understand why traditional optimism fails computationally, consider what an algorithm must do during a policy update. It must search through a massive version space of functions to find the one that maximizes the expected value.
As models move beyond simple linear representations to handle high-dimensional or non-linear structures, this optimization problem hits a wall:
- Non-Convex Constraints: In continuous or high-dimensional systems, such as the sparse linear quadratic systems studied by Javanmard et al. or the parametric exponential families analyzed by Gopalan et al., the confidence sets introduce non-convex constraints. Finding the global maximum within these boundaries becomes computationally prohibitive.
- Exhaustive Enumeration: For rich observation spaces, many sample-efficient frameworks rely on version spaces that require checking or enumerating every possible function in a large class. As noted by Dann et al. and Jin et al., this dependency makes the algorithms practically unimplementable for complex function approximators like deep neural networks.
- Combinatorial Planning Explosions: Even when the transition dynamics themselves can be learned efficiently, planning an optimal policy over those dynamics can remain intractable. For instance, Misra demonstrates that when environments feature combinatorial latent states, the planning phase itself becomes the primary computational bottleneck, independent of sample collection.
Bypassing the Oracle
To bridge this statistical-computational gap, researchers have developed alternative algorithmic frameworks that preserve the exploratory benefits of optimism without explicitly solving the intractable max-min optimization problems.
1. Randomized Exploration and Perturbation
Instead of explicitly constructing a confidence set and maximizing over it, why not let randomness do the heavy lifting? By injecting controlled noise into the training data or rewards, an agent can implicitly achieve optimism.
For general function approximation, Ishfaq et al. introduced $\mathcal{F}$-LSVI-PHE (Perturbed History Exploration). This approach perturbs historical training data with random noise and takes the maximum over multiple samples. This simple data-driven trick provides the theoretical rigor of Upper Confidence Bound (UCB) methods while utilizing standard, computationally efficient optimization routines.
Similarly, in the context of Reinforcement Learning from Human Feedback (RLHF), Wu et al. demonstrated that injecting Gaussian noise into preference updates bypasses the need to search through exponentially large policy spaces, yielding the first computationally polynomial and statistically optimal algorithms for preference-based RL.
2. Policy Covers
Another strategy replaces the global optimistic planner with a sequence of exploratory policies that collectively cover the state space.
In the PC-MLP framework proposed by Sun et al., the algorithm maintains a "policy cover"—a historical ensemble of discovered policies. Instead of demanding an oracle to find the single most optimistic path through an uncertain model, the agent uses a simple reward bonus to drive exploration toward the fringes of the policy cover. This design allows the framework to integrate seamlessly with standard, off-the-shelf, non-optimistic planning algorithms while maintaining provable sample efficiency.
3. Grounding in Standard Optimization Oracles
Rather than inventing specialized, intractable oracles to manage version spaces, modern algorithms are increasingly designed around standard, practical optimization objectives like Maximum Likelihood Estimation (MLE) or least-squares regression.
For example, in representation learning for low-rank MDPs, Uehara et al. developed REP-UCB and REP-LCB. By abandoning traditional "explore-then-commit" version spaces and anchoring the representation learning step directly to standard MLE objectives, they achieved polynomial runtime guarantees alongside sharp sample complexity bounds.
4. Environment Emulators
In settings with sparse structures, the bottleneck often stems from feature selection within the optimistic framework. Moitra et al. bypassed this entirely in sparse linear MDPs by introducing an emulator—a succinct, approximate representation of environment transitions. The emulator acts as a proxy that allows the agent to calculate near-optimal policies in polynomial time, completely avoiding the computationally intractable feature-selection oracles that plagued prior theoretical models.