# Asymptotically Optimal Bandits under Weighted Information

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 42 references that are in the map.
- First posted on arXiv 28 May 2021.

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

- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [Budget-Constrained Multi-Armed Bandits with Multiple Plays](https://mlsanity.com/paper/1711.05928/) (2017)
- [Online Learning for Active Cache Synchronization](https://mlsanity.com/paper/2002.12014/) (2020)

## Abstract (arXiv)

We study the problem of regret minimization in a multi-armed bandit setup where the agent is allowed to play multiple arms at each round by spreading the resources usually allocated to only one arm. At each iteration the agent selects a normalized power profile and receives a Gaussian vector as outcome, where the unknown variance of each sample is inversely proportional to the power allocated to that arm. The reward corresponds to a linear combination of the power profile and the outcomes, resembling a linear bandit. By spreading the power, the agent can choose to collect information much faster than in a traditional multi-armed bandit at the price of reducing the accuracy of the samples. This setup is fundamentally different from that of a linear bandit -- the regret is known to scale as Theta(√T) for linear bandits, while in this setup the agent receives a much more detailed feedback, for which we derive a tight log(T) problem-dependent lower-bound. We propose a Thompson-Sampling-based strategy, called Weighted Thompson Sampling (WTS), that designs the power profile as its posterior belief of each arm being the best arm, and show that its upper bound matches the derived logarithmic lower bound. Finally, we apply this strategy to a problem of control and system identification, where the goal is to estimate the maximum gain (also called H_∞-norm) of a linear dynamical system based on batches of input-output samples.