# Restless Bandit Problem with Rewards Generated by a Linear Gaussian Dynamical System

arXiv: https://arxiv.org/abs/2405.09584 · HTML: https://mlsanity.com/paper/2405.09584/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 26 references that are in the map.
- First posted on arXiv 15 May 2024.

## Builds on (most cited first, 8 of 8)

- [Finite Sample Analysis of Stochastic System Identification](https://mlsanity.com/paper/1903.09122/) (2019)
- [Provably Efficient Online Hyperparameter Optimization with Population-Based Bandits](https://mlsanity.com/paper/2002.02518/) (2020)
- [Time-Varying Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1601.06650/) (2016)
- [Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems](https://mlsanity.com/paper/1905.12673/) (2019)
- [Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits](https://mlsanity.com/paper/2011.02664/) (2020)
- [Non-Stationary Bandits with Auto-Regressive Temporal Dependency](https://mlsanity.com/paper/2210.16386/) (2022)
- [Stochastic Multi-armed Bandits with Non-stationary Rewards Generated by a Linear Dynamical System](https://mlsanity.com/paper/2204.05782/) (2022)
- [A Distributed Implementation of Steady-State Kalman Filter](https://mlsanity.com/paper/2101.10689/) (2021)

## Abstract (arXiv)

Decision-making under uncertainty is a fundamental problem encountered frequently and can be formulated as a stochastic multi-armed bandit problem. In the problem, the learner interacts with an environment by choosing an action at each round, where a round is an instance of an interaction. In response, the environment reveals a reward, which is sampled from a stochastic process, to the learner. The goal of the learner is to maximize cumulative reward. In this work, we assume that the rewards are the inner product of an action vector and a state vector generated by a linear Gaussian dynamical system. To predict the reward for each action, we propose a method that takes a linear combination of previously observed rewards for predicting each action's next reward. We show that, regardless of the sequence of previous actions chosen, the reward sampled for any previously chosen action can be used for predicting another action's future reward, i.e. the reward sampled for action 1 at round t-1 can be used for predicting the reward for action 2 at round t. This is accomplished by designing a modified Kalman filter with a matrix representation that can be learned for reward prediction. Numerical evaluations are carried out on a set of linear Gaussian dynamical systems and are compared with 2 other well-known stochastic multi-armed bandit algorithms.