Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics

• URL: http://arxiv.org/abs/2510.16208v1
• Date: Fri, 17 Oct 2025 20:41:14 GMT
• Title: Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics
• Authors: Sunmook Choi, Yahya Sattar, Yassir Jedra, Maryam Fazel, Sarah Dean,
• Abstract summary: We study a nonstationary bandit problem where rewards depend on both actions and latent states.<n>We propose an explore-then-commit algorithm for a finite horizon $T$.<n>Our proposed algorithm achieves $tildemathcalO(T2/3)$ regret.
• Score: 21.224078346005655
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a nonstationary bandit problem where rewards depend on both actions and latent states, the latter governed by unknown linear dynamics. Crucially, the state dynamics also depend on the actions, resulting in tension between short-term and long-term rewards. We propose an explore-then-commit algorithm for a finite horizon $T$. During the exploration phase, random Rademacher actions enable estimation of the Markov parameters of the linear dynamics, which characterize the action-reward relationship. In the commit phase, the algorithm uses the estimated parameters to design an optimized action sequence for long-term reward. Our proposed algorithm achieves $\tilde{\mathcal{O}}(T^{2/3})$ regret. Our analysis handles two key challenges: learning from temporally correlated rewards, and designing action sequences with optimal long-term reward. We address the first challenge by providing near-optimal sample complexity and error bounds for system identification using bilinear rewards. We address the second challenge by proving an equivalence with indefinite quadratic optimization over a hypercube, a known NP-hard problem. We provide a sub-optimality guarantee for this problem, enabling our regret upper bound. Lastly, we propose a semidefinite relaxation with Goemans-Williamson rounding as a practical approach.

Related papers

• Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning [13.429541377715296]
  We propose the first computationally efficient algorithm achieving rate-optimal regret guarantees in infinite-horizon discounted linear Markov decision processes.<n>We show that, combined with a regularized approximate dynamic-programming scheme, the resulting algorithm achieves a regret of order $tildemathcalO (sqrtd3 (1 - gamma)- 7 / 2 T)$, where $T$ is the total number of sample transitions, $gamma in (0,1)$ is the discount factor, and $d$ is the feature dimensionality.
  arXiv  Detail & Related papers  (2025-02-19T17:32:35Z)
• Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints [8.784438985280094]
  We study problems as pure exploration in multi-armed bandits with unknown linear constraints. First, we propose a Lagrangian relaxation of the sample complexity lower bound for pure exploration under constraints. Second, we leverage the Lagrangian lower bound and the properties of convex to propose two computationally efficient extensions of Track-and-Stop and Gamified Explorer, namely LATS and LAGEX.
  arXiv  Detail & Related papers  (2024-10-24T15:26:14Z)
• Bridging Discrete and Backpropagation: Straight-Through and Beyond [62.46558842476455]
  We propose a novel approach to approximate the gradient of parameters involved in generating discrete latent variables. We propose ReinMax, which achieves second-order accuracy by integrating Heun's method, a second-order numerical method for solving ODEs.
  arXiv  Detail & Related papers  (2023-04-17T20:59:49Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  We propose a new reward-free algorithm for learning linear Markov decision processes (MDPs) At the core of our algorithm is uncertainty-weighted value-targeted regression with exploration-driven pseudo-reward. We show that our algorithm only needs to explore $tilde O( d2varepsilon-2)$ episodes to find an $varepsilon$-optimal policy.
  arXiv  Detail & Related papers  (2023-03-17T17:53:28Z)
• ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits [20.128001589147512]
  We study the problem of non-stationary dueling bandits and provide the first adaptive dynamic regret algorithm for this problem. We show a near-optimal $tildeO(sqrtStexttCW T)$ dynamic regret bound, where $StexttCW$ is the number of times the Condorcet winner changes in $T$ rounds.
  arXiv  Detail & Related papers  (2022-10-25T20:26:02Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  Inverse reinforcement learning (IRL) aims to recover the reward function and the associated optimal policy. Many algorithms for IRL have an inherently nested structure. We develop a novel single-loop algorithm for IRL that does not compromise reward estimation accuracy.
  arXiv  Detail & Related papers  (2022-10-04T17:13:45Z)
• Break your Bandit Routine with LSD Rewards: a Last Switch Dependent Analysis of Satiation and Seasonality [6.146046338698175]
  We introduce a novel non-stationary bandit problem, where the expected reward of an arm is fully determined by the time elapsed since the arm last took part in a switch of actions. Our model generalizes previous notions of delay-dependent rewards, and also relaxes most assumptions on the reward function. We prove an algorithm and prove a bound on its regret with respect to the optimal non-stationary policy.
  arXiv  Detail & Related papers  (2021-10-22T14:53:13Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  Intrinsic rewards play a central role in handling the exploration-exploitation trade-off. We introduce emphanti-concentrated confidence bounds for efficiently approximating the elliptical bonus. We develop a practical variant for deep reinforcement learning that is competitive with contemporary intrinsic rewards on Atari benchmarks.
  arXiv  Detail & Related papers  (2021-10-21T15:25:15Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  We investigate the active pure exploration problem in Markov Decision Processes. Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
  arXiv  Detail & Related papers  (2021-06-05T09:16:28Z)
• Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation [107.06364966905821]
  We study the exploration-exploitation dilemma in the linear quadratic regulator (LQR) setting. Inspired by the extended value iteration algorithm used in optimistic algorithms for finite MDPs, we propose to relax the optimistic optimization of ofulq. We show that an $epsilon$-optimistic controller can be computed efficiently by solving at most $Obig(log (1/epsilon)big)$ Riccati equations.
  arXiv  Detail & Related papers  (2020-07-13T16:30:47Z)

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.