Dynamical Linear Bandits

• URL: http://arxiv.org/abs/2211.08997v2
• Date: Tue, 30 May 2023 10:17:22 GMT
• Title: Dynamical Linear Bandits
• Abstract summary: In many real-world sequential decision-making problems, an action does not immediately reflect on the feedback and spreads its effects over a long time frame. Previous work has investigated the Multi-Armed Bandit framework with the possibility of delayed and aggregated feedback. In this paper, we introduce a novel setting, the Dynamical Linear Bandits (DLB), an extension of the linear bandits characterized by a hidden state.
• Score: 45.3190496371625
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In many real-world sequential decision-making problems, an action does not immediately reflect on the feedback and spreads its effects over a long time frame. For instance, in online advertising, investing in a platform produces an instantaneous increase of awareness, but the actual reward, i.e., a conversion, might occur far in the future. Furthermore, whether a conversion takes place depends on: how fast the awareness grows, its vanishing effects, and the synergy or interference with other advertising platforms. Previous work has investigated the Multi-Armed Bandit framework with the possibility of delayed and aggregated feedback, without a particular structure on how an action propagates in the future, disregarding possible dynamical effects. In this paper, we introduce a novel setting, the Dynamical Linear Bandits (DLB), an extension of the linear bandits characterized by a hidden state. When an action is performed, the learner observes a noisy reward whose mean is a linear function of the hidden state and of the action. Then, the hidden state evolves according to linear dynamics, affected by the performed action too. We start by introducing the setting, discussing the notion of optimal policy, and deriving an expected regret lower bound. Then, we provide an optimistic regret minimization algorithm, Dynamical Linear Upper Confidence Bound (DynLin-UCB), that suffers an expected regret of order $\widetilde{\mathcal{O}} \Big( \frac{d \sqrt{T}}{(1-\overline{\rho})^{3/2}} \Big)$, where $\overline{\rho}$ is a measure of the stability of the system, and $d$ is the dimension of the action vector. Finally, we conduct a numerical validation on a synthetic environment and on real-world data to show the effectiveness of DynLin-UCB in comparison with several baselines.

Related papers

• Why Does Action Chunking Improve Behavioral Cloning Performance in Robotic Control? [78.81308700607651]
  Action chunking predicts and executes multiple actions instead of a single action.<n>We show that action chunking benefits from greater non-Markovian expressivity and reduced compounding error compared to Markovian policies.<n>We propose a policy class that amplifies the benefits of action chunking by explicitly instantiating an ensemble.
  arXiv  Detail & Related papers  (2026-08-03T17:32:45Z)
• Stochastic Linear Bandits with Partially Observed Actions [11.633556389435244]
  We study a partially observed variant of the linear bandit problem in which the learning agent only sees a random subset of coordinates for each action.<n>We show that this barrier can be overcome when the action vectors have low intrinsic dimension.<n>Our theory shows that TOFU-POV enjoys a $sqrtT$ regret that scales with the intrinsic action subspace dimension.
  arXiv  Detail & Related papers  (2026-07-09T22:23:17Z)
• $ω$-EVA: Envision, Verify, and Act with Latent Interactive World Models [28.544954130906135]
  Embodied policies typically map current observations directly to actions, leaving candidate-action consequences implicit.<n>We introduce $$-EVA, a latent interactive world model that realizes an Envision-Verify-Act loop for embodied action generation.<n>Its three-stage framework learns action-conditioned latent dynamics, trains a language-conditioned flow policy, and feeds the policy's proposal back through the world model.
  arXiv  Detail & Related papers  (2026-06-08T13:12:56Z)
• Self-Correcting VLA: Online Action Refinement via Sparse World Imagination [55.982504915794514]
  We propose Self-Correcting VLA (SC-VLA), which achieve self-improvement by intrinsically guiding action refinement through sparse imagination.<n>SC-VLA achieve state-of-the-art performance, yielding the highest task throughput with 16% fewer steps and a 9% higher success rate than the best-performing baselines.
  arXiv  Detail & Related papers  (2026-02-25T06:58:06Z)
• \ extsc{NaVIDA}: Vision-Language Navigation with Inverse Dynamics Augmentation [50.027425808733994]
  textscNaVIDA is a unified VLN framework that couples policy learning with action-grounded visual dynamics and adaptive execution.<n>textscNaVIDA augments training with chunk-based inverse-dynamics supervision to learn causal relationship between visual changes and corresponding actions.<n>Experiments show that textscNaVIDA achieves superior navigation performance compared to state-of-the-art methods with fewer parameters.
  arXiv  Detail & Related papers  (2026-01-26T06:16:17Z)
• Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs [63.47351876442425]
  We study episodic linear mixture MDPs with the unknown transition and adversarial rewards under full-information feedback. We propose a novel algorithm that combines the benefits of two popular methods: occupancy-measure-based and policy-based. Our algorithm enjoys an $widetildemathcalO(d sqrtH3 K + sqrtHK(H + barP_K$)$ dynamic regret, where $d$ is the feature dimension.
  arXiv  Detail & Related papers  (2024-11-05T13:55:52Z)
• Bidirectional Decoding: Improving Action Chunking via Closed-Loop Resampling [51.38330727868982]
  Bidirectional Decoding (BID) is a test-time inference algorithm that bridges action chunking with closed-loop operations. We show that BID boosts the performance of two state-of-the-art generative policies across seven simulation benchmarks and two real-world tasks.
  arXiv  Detail & Related papers  (2024-08-30T15:39:34Z)
• Sparsity-Agnostic Linear Bandits with Adaptive Adversaries [19.84322270472381]
  We study linear bandits where, in each round, the learner receives a set of actions (i.e., feature vectors) from which it chooses an element and obtains a reward. The expected reward is a fixed but unknown linear function of the chosen action. We study sparse regret bounds, that depend on the number $S$ of non-zero coefficients in the linear reward function.
  arXiv  Detail & Related papers  (2024-06-03T10:54:58Z)
• Leveraging Offline Data in Linear Latent Bandits [16.006405951752903]
  We show that $textitevery$ exchangeable and coherent stateless decision process is a latent bandit. We present a principled method to learn this subspace from short offline trajectories with guarantees. We provide two methods to leverage this subspace online: LOCAL-UCB and ProBALL-UCB.
  arXiv  Detail & Related papers  (2024-05-27T16:23:34Z)
• Last Switch Dependent Bandits with Monotone Payoff Functions [8.860629791560198]
  We take a step towards understanding the approximability of planning LSD bandits, namely, the (NP-hard) problem of computing an optimal arm-pulling strategy. In particular, we design the first efficient constant approximation algorithm for the problem and show that, under a natural monotonicity assumption on payoffs, its approximation guarantee almost matches the state-of-the-art. We develop new tools and insights for this class of problems, including a novel higher-dimensional relaxation and the technique of mirroring the evolution of virtual states.
  arXiv  Detail & Related papers  (2023-06-01T04:38:32Z)
• Autoregressive Bandits [58.46584210388307]
  We propose a novel online learning setting, Autoregressive Bandits, in which the observed reward is governed by an autoregressive process of order $k$. We show that, under mild assumptions on the reward process, the optimal policy can be conveniently computed. We then devise a new optimistic regret minimization algorithm, namely, AutoRegressive Upper Confidence Bound (AR-UCB), that suffers sublinear regret of order $widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G
  arXiv  Detail & Related papers  (2022-12-12T21:37:36Z)
• Exploration in Linear Bandits with Rich Action Sets and its Implications for Inference [23.364534479492715]
  We show that the minimum eigenvalue of the expected matrix grows as $Omega(sqrtn) whenever the expected cumulative regret of the algorithm is $sqrtn)$. We apply our result to two practical scenarios -- emphmodel selection and emphclustering in linear bandits.
  arXiv  Detail & Related papers  (2022-07-23T20:25:07Z)
• Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism [65.46524775457928]
  offline reinforcement learning seeks to utilize offline/historical data to optimize sequential decision-making strategies. We study the statistical limits of offline reinforcement learning with linear model representations.
  arXiv  Detail & Related papers  (2022-03-11T09:00:12Z)
• Robust Value Iteration for Continuous Control Tasks [99.00362538261972]
  When transferring a control policy from simulation to a physical system, the policy needs to be robust to variations in the dynamics to perform well. We present Robust Fitted Value Iteration, which uses dynamic programming to compute the optimal value function on the compact state domain. We show that robust value is more robust compared to deep reinforcement learning algorithm and the non-robust version of the algorithm.
  arXiv  Detail & Related papers  (2021-05-25T19:48:35Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  We study a novel variant of online finite-horizon Markov Decision Processes with adversarially changing loss functions and initially unknown dynamics. In each episode, the learner suffers the loss accumulated along the trajectory realized by the policy chosen for the episode, and observes aggregate bandit feedback. Our main result is a computationally efficient algorithm with $O(sqrtK)$ regret for this setting, where $K$ is the number of episodes.
  arXiv  Detail & Related papers  (2021-01-31T16:49:07Z)
• Online Sparse Reinforcement Learning [60.44832065993122]
  We investigate the hardness of online reinforcement learning in fixed horizon, sparse linear decision process (MDP) We show that linear regret is generally unavoidable in this case, even if there exists a policy that collects well-conditioned data. This shows that in the large-action setting, the difficulty of learning can be attributed to the difficulty of finding a good exploratory policy.
  arXiv  Detail & Related papers  (2020-11-08T16:47:42Z)
• Nonstationary Reinforcement Learning with Linear Function Approximation [19.521419943509784]
  We consider reinforcement learning in episodic Markov decision processes (MDPs) with linear function approximation under drifting environment. We first develop an optimistic modification of least-squares value with periodic restart, and bound its dynamic regret when variation budgets are known. We derive the first minimax dynamic regret lower bound for nonstationary linear MDPs and as a byproduct establish a minimax regret lower bound for linear MDPs unsolved by Jin et al.
  arXiv  Detail & Related papers  (2020-10-08T20:07:44Z)

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.