An Exploration-free Method for a Linear Stochastic Bandit Driven by a Linear Gaussian Dynamical System

Jonathan Gornet, Yilin Mo, Bruno Sinopoli · 2025

Read An Exploration-free Method for a Linear Stochastic Bandit Driven by a Linear Gaussian Dynamical System by Jonathan Gornet, Yilin Mo, Bruno Sinopoli (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-03926.txt.

Introduction

Jonathan Gornet, Yilin Mo, and Bruno Sinopoli propose an exploration-free method for a linear stochastic bandit driven by a dynamical system. Their 2025 arXiv paper removes the usual explore-exploit dilemma. Rewards here are outputs of a linear Gaussian system. Hyperparameter tuning for reinforcement learning motivated the setting. Actions there far outnumber the training runs available.

Their KODE method picks actions straight from Kalman filter predictions. No deliberate exploration rounds are spent at all. Performance depends on how observable the system is. Regret is measured against the best possible action sequence. Observability properties set the achievable guarantees. The analysis ties control theory to bandit performance. Tuning budgets stretch further when every run exploits knowledge.

Catalog record

CREATORJonathan Gornet, Yilin Mo, Bruno Sinopoli
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-03926

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Exploration-free Method for a Linear Stochastic Bandit Driven by a Linear Gaussian Dynamical System Thanks: Jonathan Gornet, Yilin Mo, Bruno Sinopoli Abstract In stochastic multi-armed bandits, a major problem the learner faces is the trade-off between exploration and exploitation. Recently, exploration-free methods—methods that commit to the action predicted to return the highest reward—have been studied from the perspective of linear bandits. In this paper, we introduce a linear bandit setting where the reward is the output of a linear Gaussian dynamical system. Motivated by a problem encountered in hyperparameter optimization for reinforcement learning, where the number of actions is much higher than the number of training iterations, we propose Kalman filter Observability Dependent Exploration (KODE), an exploration-free method that utilizes the Kalman filter predictions to select actions. Our major contribution of this work is our analysis of the performance of the proposed method, which is dependent on the observability properties of the underlying linear Gaussian dynamical system. We evaluate KODE via two different metrics: regret, which is the cumulative expected difference between the highest possible reward and the reward sampled by KODE, and action alignment, which measures how closely KODE’s chosen action aligns with the linear Gaussian dynamical system’s state variable. To provide intuition on the performance, we prove that KODE implicitly encourages the learner to explore actions depending on the observability of the linear Gaussian dynamical system. This method is compared to several well-known stochastic multi-armed bandit algorithms to validate our theoretical results. I Introduction Decision-making under uncertainty is an important real-world problem. Previous work that has rigorously focused on this problem includes the Stochastic Multi-Armed Bandit (SMAB) problem, which consists of the interaction between a learner and an environment [ 1 ] . For each interaction, called a round, the learner selects an action and in response the environment samples the reward from a distribution dependent on the chosen action. The learner’s goal is to maximize the accumulated reward for a horizon length, which is the total number of interactions between the learner and the environment. The metric for measuring performance of a proposed method in SMAB is regret, which is the cumulative expected difference between the highest possible reward and the sampled reward from the method’s chosen action for each round. The SMAB commonly encounters the problem of exploration —gathering information about the actions—versus exploitation —committing to actions that are predicted to return the highest reward. A well-known principle for addressing this problem is the principle of optimism in the face of uncertainty—the learner assumes that the reward output of each action is the highest plausible predicted reward given a set confidence level—which was implemented in the Upper Confidence Bound (UCB) algorithm in [ 2 ] . More recently, results in SMAB have focused on exploration-free methods, or methods that refrain from exploring all the actions explicitly. These methods are motivated by situations where the number of actions is greater than the number of rounds in [ 3 ] . Additionally, in some linear bandit environments—where the reward is the inner product of an unknown parameter vector and a known chosen action vector—changes in the environment can induce exploration even in exploration-free methods. For example, an adversary changing the unknown parameter vector each round promotes the exploration-free method to sample uncertain actions, as shown in [ 4 ] . Another example is when the unknown parameter vector stochastically changes each round, driving exploration, which is analyzed in [ 5 ] . This has led to the development of methods that adaptively choose when to explore such as [ 6 ] . The work above highlights the need for analyzing exploration-free methods in different SMAB environments. Inspired by a classical problem of hyperparameter optimization in machine learning (see HyperBand in [ 7 ] ), in this paper we propose and analyze an exploration-free method for a linear bandit environment where the reward is the output of a known Linear Gaussian Dynamical System (LGDS). In other words, the reward is the inner product of an action vector and the LGDS state variable. By proposing this environment, we envision that the results can be used for hyperparameter optimization during training of reinforcement learning neural networks as the authors [ 8 ] —inspired by theoretical results in [ 9 ] —have modeled the problem similarly to a LGDS. In this environment, the number of actions—where an action is a hyperparameter configuration—is much larger than the number of training iterations, making it intractable to explore all the actions. The paper’s contributions are as follows. We propose a linear bandit SMAB problem where the reward is the output of a known LGDS—inner product of an action vector and the LGDS state variable. We assume that the actions, which are a set of vectors, have a \ell_{2} norm of 1. Our main contribution is the analysis of our proposed exploration-free method, called the Kalman filter Observability Dependent Exploration (KODE), which chooses actions that align most closely with the Kalman filter state prediction. KODE’s performance is first analyzed via two different metrics. The first analysis is the performance with respect to regret, which is the cumulative expected difference between the optimal reward and the sampled reward based on the learner’s chosen action. The following analysis focuses on how closely the learner’s action aligns with the optimal action at each round, which is dependent on the LGDS parameters. Following the performance analysis, we discuss how KODE has an implicit exploration term that perturbs the learner to explore depending on the observability of the LGDS. We provide numerical results validating KODE’s performance based on our theoretical predictions. The layout of the paper is as follows. For Section II , the proposed environment is formulated. For Section III , we introduce KODE. Subsection III-A will provide performance analyses of KODE and Subsection III-B will discuss how properties of the LGDS promote exploration in KODE. Numerical results will be presented in Section IV . The paper is concluded with discussions of future directions in Section V . I-A Related Work In this paper, the proposed environment is based on the linear bandit. In linear bandits, recent studies have developed algorithms for when the unknown parameter vector changes such as [ 10 , 11 , 12 ] . In [ 10 ] , the authors address the case when the changes in the unknown parameter vector are bounded by proposing a sliding-window algorithm that uses the samples collected within a window for estimating the unknown parameter vector. For [ 11 ] , the environment changes slightly where now the norm of the unknown parameter vector is bounded. The algorithm proposed in [ 11 ] restarts after a set number of rounds. Finally, for [ 12 ] , the authors tackle the adversarial and stochastic case of the linear bandit, where the adversarial case is when the unknown parameter vector is chosen by an adversary prior to each learner’s interaction. In this work, the authors used a Follow-the-Regularized Leader approach, which is when the learner chooses actions based on what was the optimal action the previous round with a regularizer [ 1 ] . A variation of the SMAB relevant to this paper is the non-stationary SMAB problem, where the

Read the complete text