Learning when to take advice: a statistical test for achieving a correlated equilibrium

Greg Hines, Kate Larson
Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, PMLR R6:274-281, 2008.

Abstract

We study a multiagent learning problem where agents can either learn via repeated interactions, or can follow the advice of a mediator who suggests possible actions to take. We present an algorithm that each agent can use so that, with high probability, they can verify whether or not the mediator’s advice is useful. In particular, if the mediator’s advice is useful then agents will reach a correlated equilibrium, but if the mediator’s advice is not useful, then agents are not harmed by using our test, and can fall back to their original learning algorithm. We then generalize our algorithm and show that in the limit it always correctly verifies the mediator’s advice.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR6-hines08a, title = {Learning when to take advice: a statistical test for achieving a correlated equilibrium}, author = {Hines, Greg and Larson, Kate}, booktitle = {Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence}, pages = {274--281}, year = {2008}, editor = {McAllester, David A. and Myllymäki, Petri}, volume = {R6}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r6/main/assets/hines08a/hines08a.pdf}, url = {https://proceedings.mlr.press/r6/hines08a.html}, abstract = {We study a multiagent learning problem where agents can either learn via repeated interactions, or can follow the advice of a mediator who suggests possible actions to take. We present an algorithm that each agent can use so that, with high probability, they can verify whether or not the mediator’s advice is useful. In particular, if the mediator’s advice is useful then agents will reach a correlated equilibrium, but if the mediator’s advice is not useful, then agents are not harmed by using our test, and can fall back to their original learning algorithm. We then generalize our algorithm and show that in the limit it always correctly verifies the mediator’s advice.}, note = {Reissued by PMLR on 09 October 2024.} }
Endnote
%0 Conference Paper %T Learning when to take advice: a statistical test for achieving a correlated equilibrium %A Greg Hines %A Kate Larson %B Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2008 %E David A. McAllester %E Petri Myllymäki %F pmlr-vR6-hines08a %I PMLR %P 274--281 %U https://proceedings.mlr.press/r6/hines08a.html %V R6 %X We study a multiagent learning problem where agents can either learn via repeated interactions, or can follow the advice of a mediator who suggests possible actions to take. We present an algorithm that each agent can use so that, with high probability, they can verify whether or not the mediator’s advice is useful. In particular, if the mediator’s advice is useful then agents will reach a correlated equilibrium, but if the mediator’s advice is not useful, then agents are not harmed by using our test, and can fall back to their original learning algorithm. We then generalize our algorithm and show that in the limit it always correctly verifies the mediator’s advice. %Z Reissued by PMLR on 09 October 2024.
APA
Hines, G. & Larson, K.. (2008). Learning when to take advice: a statistical test for achieving a correlated equilibrium. Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R6:274-281 Available from https://proceedings.mlr.press/r6/hines08a.html. Reissued by PMLR on 09 October 2024.

Related Material