Infrequent Exploration in Linear Bandits

• URL: http://arxiv.org/abs/2510.26000v1
• Date: Wed, 29 Oct 2025 22:25:43 GMT
• Title: Infrequent Exploration in Linear Bandits
• Abstract summary: We introduce a simple and practical framework, INFEX, explicitly designed for infrequent exploration.<n> INFEX executes a base exploratory policy according to a given schedule while predominantly choosing greedy actions in between.<n>Our theoretical analysis demonstrates that INFEX achieves instance-dependent regret matching standard provably efficient algorithms.
• Score: 39.8867004581646
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study the problem of infrequent exploration in linear bandits, addressing a significant yet overlooked gap between fully adaptive exploratory methods (e.g., UCB and Thompson Sampling), which explore potentially at every time step, and purely greedy approaches, which require stringent diversity assumptions to succeed. Continuous exploration can be impractical or unethical in safety-critical or costly domains, while purely greedy strategies typically fail without adequate contextual diversity. To bridge these extremes, we introduce a simple and practical framework, INFEX, explicitly designed for infrequent exploration. INFEX executes a base exploratory policy according to a given schedule while predominantly choosing greedy actions in between. Despite its simplicity, our theoretical analysis demonstrates that INFEX achieves instance-dependent regret matching standard provably efficient algorithms, provided the exploration frequency exceeds a logarithmic threshold. Additionally, INFEX is a general, modular framework that allows seamless integration of any fully adaptive exploration method, enabling wide applicability and ease of adoption. By restricting intensive exploratory computations to infrequent intervals, our approach can also enhance computational efficiency. Empirical evaluations confirm our theoretical findings, showing state-of-the-art regret performance and runtime improvements over existing methods.

Related papers

• Constrained Bayesian Optimisation with Multiple Information Sources [1.424507155580441]
  We propose a general multi-source framework that extends constrained Max-value Entropy Search.<n>We show that our method efficiently identifies feasible and optimal solutions, even when auxiliary data are only weakly correlated.<n>The proposed approach consistently outperforms existing methods, particularly in early-stage exploration.
  arXiv  Detail & Related papers  (2026-07-01T12:31:15Z)
• RIE-Greedy: Regularization-Induced Exploration for Contextual Bandits [4.282654316889406]
  Real-world contextual bandit problems with complex reward models are often tackled with iteratively trained models, such as boosting trees.<n>Existing approaches rely on sophisticated assumptions or intractable procedures that are hard to verify and implement in practice.<n>In this work, we explore the use of an exploration-free (pure-greedy) action selection strategy, that exploits the randomness inherent in model fitting process as an intrinsic source of exploration.
  arXiv  Detail & Related papers  (2026-03-11T20:11:01Z)
• Think Longer to Explore Deeper: Learn to Explore In-Context via Length-Incentivized Reinforcement Learning [53.58654277639939]
  In-context exploration is the intrinsic ability to generate, verify, and refine hypotheses within a single continuous context.<n>We propose Length-Incentivized Exploration, which explicitly encourages models to explore more.<n>Our method achieves an average improvement of 4.4% on in-domain tasks and a 2.7% gain on out-of-domain benchmarks.
  arXiv  Detail & Related papers  (2026-02-12T09:24:32Z)
• CausalCompass: Evaluating the Robustness of Time-Series Causal Discovery in Misspecified Scenarios [17.11442807888366]
  Causal is a benchmark suite designed to assess the robustness of time-series causal discovery methods under violations of modeling assumptions.<n>We conduct extensive benchmarking of representative TSCD algorithms across eight assumption-violation scenarios.<n>The methods exhibiting superior overall performance across diverse scenarios are almost deep learning-based approaches.
  arXiv  Detail & Related papers  (2026-02-08T11:27:06Z)
• Differentiable Constraint-Based Causal Discovery [18.720260801912346]
  Causal discovery from observational data is a fundamental task in artificial intelligence.<n>Existing methods can be broadly categorized as constraint-based or score-based approaches.<n>This work explores developing differentiable $d$-separation scores, obtained through a percolation theory using soft logic.
  arXiv  Detail & Related papers  (2025-10-24T21:28:39Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• Provably Efficient Exploration in Inverse Constrained Reinforcement Learning [12.178081346315523]
  Inverse Constrained Reinforcement Learning is a common solver for recovering feasible constraints in complex environments.<n>We propose a strategic exploration framework for sampling with guaranteed efficiency to bridge this gap.<n>We introduce two exploratory algorithms to achieve efficient constraint inference.
  arXiv  Detail & Related papers  (2024-09-24T10:48:13Z)
• REX: Rapid Exploration and eXploitation for AI Agents [103.68453326880456]
  We propose an enhanced approach for Rapid Exploration and eXploitation for AI Agents called REX. REX introduces an additional layer of rewards and integrates concepts similar to Upper Confidence Bound (UCB) scores, leading to more robust and efficient AI agent performance.
  arXiv  Detail & Related papers  (2023-07-18T04:26:33Z)
• Latent State Marginalization as a Low-cost Approach for Improving Exploration [79.12247903178934]
  We propose the adoption of latent variable policies within the MaxEnt framework. We show that latent variable policies naturally emerges under the use of world models with a latent belief state. We experimentally validate our method on continuous control tasks, showing that effective marginalization can lead to better exploration and more robust training.
  arXiv  Detail & Related papers  (2022-10-03T15:09:12Z)
• On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
  We study a bandit problem with a general unknown reward function and a general unknown constraint function. We propose a general framework for both algorithm performance analysis. We demonstrate the superior performance of our proposed algorithms via numerical experiments.
  arXiv  Detail & Related papers  (2022-03-29T14:02:03Z)
• False Correlation Reduction for Offline Reinforcement Learning [115.11954432080749]
  We propose falSe COrrelation REduction (SCORE) for offline RL, a practically effective and theoretically provable algorithm. We empirically show that SCORE achieves the SoTA performance with 3.1x acceleration on various tasks in a standard benchmark (D4RL)
  arXiv  Detail & Related papers  (2021-10-24T15:34:03Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  We show how iteration under a more standard notion of low inherent Bellman error, typically employed in least-square value-style algorithms, can provide strong PAC guarantees on learning a near optimal value function. We present a computationally tractable algorithm for the reward-free setting and show how it can be used to learn a near optimal policy for any (linear) reward function.
  arXiv  Detail & Related papers  (2020-08-18T04:34:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.