# Reward Maximization Under Uncertainty: Leveraging Side-Observations on Networks

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2017.

## Built on by (most cited first, 8 of 8)

- [A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00557/) (2022)
- [Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs](https://mlsanity.com/paper/2210.01376/) (2022)
- [Kolmogorov-Smirnov Test-Based Actively-Adaptive Thompson Sampling for Non-Stationary Bandits](https://mlsanity.com/paper/2105.14586/) (2021)
- [Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality](https://mlsanity.com/paper/2206.10022/) (2022)
- [Graph Feedback Bandits on Similar Arms: With and Without Graph Structures](https://mlsanity.com/paper/2501.14314/) (2025)
- [Graph Feedback Bandits with Similar Arms](https://mlsanity.com/paper/2405.11171/) (2024)
- [An LP-based Sampling Policy for Multi-Armed Bandits with Side-Observations and Stochastic Availability](https://mlsanity.com/paper/2603.26647/) (2026)
- [Learning When to Update: A Near-Optimal Timing Bandit Approach](https://mlsanity.com/paper/2609.37932/) (2026)

## Abstract (arXiv)

We study the stochastic multi-armed bandit (MAB) problem in the presence of side-observations across actions that occur as a result of an underlying network structure. In our model, a bipartite graph captures the relationship between actions and a common set of unknowns such that choosing an action reveals observations for the unknowns that it is connected to. This models a common scenario in online social networks where users respond to their friends' activity, thus providing side information about each other's preferences. Our contributions are as follows: 1) We derive an asymptotic lower bound (with respect to time) as a function of the bi-partite network structure on the regret of any uniformly good policy that achieves the maximum long-term average reward. 2) We propose two policies - a randomized policy; and a policy based on the well-known upper confidence bound (UCB) policies - both of which explore each action at a rate that is a function of its network position. We show, under mild assumptions, that these policies achieve the asymptotic lower bound on the regret up to a multiplicative factor, independent of the network structure. Finally, we use numerical examples on a real-world social network and a routing example network to demonstrate the benefits obtained by our policies over other existing policies.