Towards Fundamental Limits of Multi-armed Bandits with Random Walk Feedback
arXiv:2011.01445
Abstract
In this paper, we consider a new Multi-Armed Bandit (MAB) problem where arms are nodes in an unknown and possibly changing graph, and the agent (i) initiates random walks over the graph by pulling arms, (ii) observes the random walk trajectories, and (iii) receives rewards equal to the lengths of the walks. We provide a comprehensive understanding of this problem by studying both the stochastic and the adversarial setting. We show that this problem is not easier than a standard MAB in an information theoretical sense, although additional information is available through random walk trajectories. Behaviors of bandit algorithms on this problem are also studied.
arXiv commentmajor revision
References in corpus (13)
- A Contextual-Bandit Approach to Personalized News Article Recommendation
- Analysis of Thompson Sampling for the multi-armed bandit problem
- On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
- Contextual Bandits with Similarity Information
- Empirical Bernstein Bounds and Sample Variance Penalization
- Random matrices: Universality of local spectral statistics of non-Hermitian matrices
- The best of both worlds: stochastic and adversarial bandits
- Efficient learning by implicit exploration in bandit problems with side observations
- A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences
- Combinatorial Multi-Armed Bandit with General Reward Functions
- Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
- From Bandits to Experts: A Tale of Domination and Independence
- Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection