Linear Contextual Bandits with Quasi-Optimism

Linear contextual bandit algorithms are typically built around pointwise optimism: the exploration bonus is chosen large enough to upper-bound the value of every action with high probability. We study an alternative principle of quasi-optimism, in which the index is deliberately allowed to be smaller than a valid confidence bound. We analyze the algorithmic framework, EQOL, that replaces the usual confidence-radius bonus with the capped quadratic bonus min(c₁,t ‖x‖²_{Vt⁻¹}, c₂,t ‖x‖{Vt⁻¹}). This index is generally not optimistic, since its quadratic branch can be pointwise smaller than the OFUL bonus. We prove a general regret bound for arbitrary schedules (c₁,t, c₂,t), separating the exploration cost from the quasi-optimistic residual. With a single gap-agnostic tuning, EQOL recovers the high-probability minimax O(d√T) regret bound and, under a positive contextual margin, a uniform gap-dependent O(d²/Δmin,T) bound. We also provide a geometric interpretation of EQOL through action-dependent ellipsoids, clarifying how quasi-optimism differs from simply shrinking a UCB bonus. Experiments on synthetic and real-data contextual bandit benchmarks show that EQOL substantially outperforms existing algorithms.