Online learning with Erdos-Renyi side-observation graphs

Tomáš Kocák, Gergely Neu, Michal Valko
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:544-551, 2016.

Abstract

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 an unknown probability r_t, independently of each other and the action of the learner. Moreover, we allow r_t to change in every round t, which rules out the possibility of estimating r_t by a well-concentrated sample average. We propose an algorithm which operates under the assumption that r_t is large enough to warrant at least one side observation with high probability. We show that after T rounds in a bandit problem with N arms, the expected regret of our algorithm is of order O(\sqrt{\sum_{t=1}^T (1/r_t) \log N }), given that r_t\ge \log T / (2N-2) for all t. All our bounds are within logarithmic factors of the best achievable performance of any algorithm that is even allowed to know exact values of r_t.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-kocak16a, title = {Online learning with Erdos-Renyi side-observation graphs}, author = {Koc{\'a}k, Tom{\'a}{\v{s}} and Neu, Gergely and Valko, Michal}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {544--551}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/kocak16a/kocak16a.pdf}, url = {https://proceedings.mlr.press/r14/kocak16a.html}, abstract = {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 an unknown probability r_t, independently of each other and the action of the learner. Moreover, we allow r_t to change in every round t, which rules out the possibility of estimating r_t by a well-concentrated sample average. We propose an algorithm which operates under the assumption that r_t is large enough to warrant at least one side observation with high probability. We show that after T rounds in a bandit problem with N arms, the expected regret of our algorithm is of order O(\sqrt{\sum_{t=1}^T (1/r_t) \log N }), given that r_t\ge \log T / (2N-2) for all t. All our bounds are within logarithmic factors of the best achievable performance of any algorithm that is even allowed to know exact values of r_t.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Online learning with Erdos-Renyi side-observation graphs %A Tomáš Kocák %A Gergely Neu %A Michal Valko %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-kocak16a %I PMLR %P 544--551 %U https://proceedings.mlr.press/r14/kocak16a.html %V R14 %X 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 an unknown probability r_t, independently of each other and the action of the learner. Moreover, we allow r_t to change in every round t, which rules out the possibility of estimating r_t by a well-concentrated sample average. We propose an algorithm which operates under the assumption that r_t is large enough to warrant at least one side observation with high probability. We show that after T rounds in a bandit problem with N arms, the expected regret of our algorithm is of order O(\sqrt{\sum_{t=1}^T (1/r_t) \log N }), given that r_t\ge \log T / (2N-2) for all t. All our bounds are within logarithmic factors of the best achievable performance of any algorithm that is even allowed to know exact values of r_t. %Z Reissued by PMLR on 04 October 2026.
APA
Kocák, T., Neu, G. & Valko, M.. (2016). Online learning with Erdos-Renyi side-observation graphs. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:544-551 Available from https://proceedings.mlr.press/r14/kocak16a.html. Reissued by PMLR on 04 October 2026.

Related Material