Source-linked AI summary
Leveraging Side Observations in Stochastic Bandits
Stephane Caron, Branislav Kveton, Marc Lelarge, Smriti Bhagat
TL;DR
Standard bandits trade off exploration and exploitation, while side observations also reveal rewards for related actions. The paper develops UCB policies that use this information; on real social-network datasets, they achieve learning-rate speedups of 2.2× to 14×.
Problem
Standard bandits face an exploration–exploitation tradeoff, and their regret bound scales linearly with the number of arms K.
Source: §1 · p. 1, §3.1 · p. 3Method
UCB-N and UCB-MaxN use side observations of related-action rewards to improve stochastic-bandit regret bounds.
Source: §1 · p. 1Results
Takeaways & Limitations
The policies significantly improve learning rates when the side-observation graph is a dense social network.
Source: §6 · p. 9The most appropriate subgraph structure for the problem remains an open question.
Source: §6 · p. 9
Abstract
from arXiv · showhide
This paper considers stochastic bandits with side observations, a model that accounts for both the exploration/exploitation dilemma and relationships between arms. In this setting, after pulling an arm i, the decision maker also observes the rewards for some other actions related to i. We will see that this model is suited to content recommendation in social networks, where users' reactions may be endorsed or not by their friends. We provide efficient algorithms based on upper confidence bounds (UCBs) to leverage this additional information and derive new bounds improving on standard regret guarantees. We also evaluate these policies in the context of movie recommendation in social networks: experiments on real datasets show substantial learning rate speedups ranging from 2.2x to 14x on dense networks.
1 INTRODUCTION
Stochastic bandits balance exploration and exploitation, but side observations let a chosen action also reveal rewards for related actions. The paper develops UCB policies for this setting and reports improved regret bounds and faster learning on dense social networks.
1 INTRODUCTION
- UCB1 achieves logarithmic expected regret, yielding an expected mean loss per decision of O(ln n/n).The paper describes this scaling as optimal.Source: §1 · p. 1
- Side observations provide information about related actions when an action is played, as in social promotions where a user's friends may react to the content.The provider receives the targeted user's reward and observes friends' reactions, such as likes.Source: §1 · p. 1
- 2.2× to 14× learning-rate speedups were observed for the proposed policies on real social-network datasets.The paper highlights dense reward structures and large numbers of arms as settings where the improvements are significant.Source: §1 · p. 1
- UCB-N extends UCB1 to use side observations, reducing the regret-bound coefficient, while UCB-MaxN further improves the bound's constant term.The paper reports both improvements as significant for large numbers of arms and dense reward structures.Source: §1 · p. 1
2 RELATED WORK
Prior work studies stochastic bandits through regret-optimal UCB policies and structured reward models, while contextual side information is distinct from observing related-action rewards after a pull. Side observations had also been studied in adversarial bandits, whose regret guarantees differ from the stochastic setting.
2 RELATED WORK
- UCB policies use upper confidence bounds to choose arms, and UCB1 achieves an optimal logarithmic bound uniformly over time.Earlier stochastic-bandit work established a logarithmic lower bound; later work improved UCB1's constants under additional statistical assumptions.Source: §2 · p. 2
- Structured stochastic-bandit approaches address many arms by assuming reward similarity, such as nearby arms sharing reward processes or mean rewards following Lipschitz or linear structure.X-armed and linear bandits are examples with potentially infinitely many arms.Source: §2 · p. 2
- Mannor et al. [16] studied side observations in adversarial bandits; this paper instead uses stochastic reward assumptions to derive O(ln n) regret bounds rather than the adversarial eO(√n) guarantees.The related work describes ExpBan as using a clique decomposition and ELP as extending EXP3 to account for side observations.Source: §2 · p. 2
- Contextual side information is available before an arm is pulled, unlike this paper's side observations of related-action rewards.The cited contextual-bandit work provides asymptotically optimal policies for two-armed bandits.Source: §2 · p. 2
3 SIDE OBSERVATIONS
The section defines side observations through a graph linking arms whose rewards are observed together, then analyzes regret bounds and a UCB policy that uses those additional observations.
3 SIDE OBSERVATIONS
- The side-observation graph connects arms whose rewards are observed together, and a clique covering partitions the analysis across groups of mutually connected arms.The observation count for an arm includes observations obtained by pulling that arm or one of its neighbors.Source: §3 · p. 3
3.1 LOWER BOUND
- If some arms cannot be observed by pulling an optimal arm, every uniformly good allocation rule has expected regret at least Ω(ln n).The stated condition is that the neighborhoods of the optimal arms do not cover all arms.Source: §3.1 · p. 3
3.3 UCB-N POLICY
- UCB-N selects the arm with the largest UCB and updates estimates for every arm observed after the selected pull.The section states an expected-regret upper bound for UCB-N and explains that summing clique-level bounds over a covering yields the overall bound.Source: §3.3 · pp. 4–5
3.2 UPPER CONFIDENCE BOUNDS
- UCB-N’s regret bound uses a clique covering of the observation graph, and its trivial singleton covering recovers the UCB1 bound.The bound takes an infimum over possible clique coverings; the section also introduces a second algorithm to improve the O(K) constant, with factors scaling as O(|C|).Source: §3.2 · p. 4, §3.3 · p. 5
4 UCB-MaxN POLICY
UCB-MaxN separates choosing which arm to observe from choosing which arm to pull, using side observations to improve the regret bound. Its bound asymptotically reduces a factor from O(K) to O(|C|), where C is an optimal clique covering of the side-observation graph.
4 UCB-MaxN POLICY
- The second case for selecting an arm is high uncertainty, which can be reduced by pulling a neighbor rather than the arm itself.In that case, the policy can choose a neighbor with higher empirical rewards; when an arm is selected for a high average estimate, it is already best in its observation set.Source: §4 · p. 5
- UCB-MaxN first chooses an arm to observe by UCB, then pulls the arm with the highest empirical mean in that observation set.The policy uses the UCB choice to target information and the empirical-mean choice to select the pull.Source: §4 · p. 5
- Asymptotically, UCB-MaxN reduces the second factor in the regret upper bound from O(K) to O(|C|), for an optimal clique covering C of the side-observation graph.Theorem 3 gives an expected regret upper bound for UCB-MaxN.Source: §4 · p. 5
- The bound is uniform over time, but its final term can be large for small n and pathological regret distributions.In the Flixster experiment, that term was below the stated constant for more than 80% of cliques after about 20K steps.Source: §4 · p. 6
5 EXPERIMENTS
Experiments on Flixster and Facebook assess UCB-N and UCB-MaxN against bandit baselines for movie recommendations, including settings with friend-of-friend observations. The policies show lower regret in denser settings, while the evaluation also examines clique-cover size and overlap.
5.1 DATASETS
- The evaluation uses Flixster movie ratings and a Facebook subset; Flixster preprocessing yields 5K users, 5K movies, and 1.7M ratings, while the Facebook subgraph has 14K users and 500K edges.Source: §5.1 · p. 7
5.2 EXPERIMENTAL SETUP
- The recommendation simulation samples a new movie each turn, rewards a positive rating above 3.5 stars, and treats friends’ opinions as side observations.The same movie is assumed never to be sampled twice.Source: §5.2 · p. 7
- Because minimum clique cover is NP-hard, the evaluation builds a maximal clique around each vertex and greedily selects a cover, then tests subgraphs at 3%, 15%, and 100% coverage.The smaller covers focus on dense, active regions under the biggest-cliques-first heuristic.Source: §5.2 · p. 7
- The plots measure per-step regret and mark the number of cliques in the cover, the steps needed to pull every arm once; policies perform approximately alike before that mark.Source: §5.2 · p. 7
5.3.1 FRIENDS OF FRIENDS
- With friend-of-friend observations on Flixster, the gap between the baselines and the proposed policies widened; eight cliques covered 15% of the graph, 20 times fewer than in the earlier setting.Source: Figure 2 · p. 8, §5.3.1 · p. 8
5.3 FLIXSTER
- On Flixster, UCB-N and UCB-MaxN had significantly lower regret than UCB1 and UCB1-on-cliques; ε-greedy also improved but deteriorated faster as the cover grew.Source: §5.3 · p. 8
- For Flixster covers of 3%, 15%, and 100%, UCB-MaxN’s regret was 9%, 3%, and 33% smaller than UCB-N’s, respectively, as average clique overlap varied.The average number of cliques covering an arm was 1.18, 1.09, and 1.76 for those covers, respectively.Source: §5.3 · p. 8
5.4 FACEBOOK
- On Facebook with friend-of-friend observations, UCB-MaxN’s regret was 10 times smaller than UCB1-on-cliques and UCB-N for the 15% cover.Five friend-of-friend cliques covered 15% of this graph; the paper reports smaller regrets overall on Facebook than Flixster, essentially because Facebook is denser.Source: Figure 4 · p. 9, §5.4 · p. 9
6 CONCLUSION AND FUTURE WORK
The paper introduces UCB-N and UCB-MaxN for stochastic bandits with side observations. It reports improved regret bounds and learning rates on dense social-network graphs, while leaving the best subgraph structure for analysis open.
6 CONCLUSION AND FUTURE WORK
- UCB-N and UCB-MaxN leverage side observations to produce substantial learning-rate speedups.Source: §6 · p. 9
- The policies reduce regret-bound factors from O(K) to O(|C|), an improvement for dense reward-dependency structures, and experiments suggest faster learning on dense social-network graphs.Source: §6 · p. 9
- Although the algorithms use neighborhoods rather than cliques, the most appropriate subgraph structure for tighter bounds and more efficient policies remains an open question.Source: §6 · p. 9