Search papers, labs, and topics across Lattice.
This paper studies adversarial multi-armed bandit problems where the learner observes losses of non-chosen arms with an unknown probability *r*. Two algorithms are proposed, each tailored to different ranges of *r*, to minimize regret. The first algorithm achieves $O(\sqrt{(T /r) \log N })$ regret when $r\ge(\log T)/(2N)$, while the second achieves $O(\sqrt{(T/r) \log (N+T)})$ for smaller *r*, both within logarithmic factors of the optimal regret.
Learning in multi-armed bandits gets a boost: even with only probabilistic side observations of other arms' losses, near-optimal regret is achievable without knowing the observation probability.
We consider adversarial multi-armed bandit problems where the learner is allowed to observe losses of a number of arms beside the arm that it actually chose. We study the case where all non-chosen arms reveal their loss with a fixed but unknown probability $r$, independently of each other and the action of the learner. We propose two algorithms that work for different ranges of $r$. We show that after $T$ rounds in a bandit problem with $N$ arms, the expected regret of our first algorithm is $O(\sqrt{(T /r) \log N })$ whenever $r\ge(\log T)/(2N)$, while our second algorithm achieves a regret of $O(\sqrt{(T/r) \log (N+T)})$ for smaller values of $r$. We also give a quick estimation procedure that decides the range of~$r$. All our bounds are within logarithmic factors of the best achievable performance of any algorithm that is even allowed to know~$r$.
