| Abstract |
Most multi-armed bandit and reinforcement learning algorithms typically rely on full optimism, using confidence bonuses large enough to upper-bound unknown values with high probability. This talk presentsquasi-optimism, a new exploration principle that permits a controlled degree of underestimation while retaining provably optimal regret guarantees. We first introduce the principle in tabular reinforcement learning, where a simple inverse-count bonus achieves minimax-optimal regret without empirical-variance estimation, and then discuss its extension to distributional and instance-dependent regret guarantees in bandits and reinforcement learning. Finally, we extend quasi-optimism to linear contextual bandits through a quadratic–linear bonus. Despite not being pointwise optimistic, the new linear bandit algorithm simultaneously achieves minimax and margin-dependent regret guarantees under a single gap-agnostic tuning, while substantially reducing unnecessary exploration in empirical evaluations. Together, these results suggest that full optimism is not necessary for exploration to be both theoretically optimal and practically effective.
This talk is based on the following recent works:
Oh & Lee,Linear Contextual Bandits with Quasi-Optimism, 2026.
Lee & Oh, Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning, COLT 2026.Lee & Oh,Minimax Optimal Reinforcement Learning with Quasi-Optimism, ICLR 2025. |
