Hedged learning: regret-minimization with learning experts

ABSTRACT

In non-cooperative multi-agent situations, there cannot exist a globally optimal, yet opponent-independent learning algorithm. Regret-minimization over a set of strategies optimized for potential opponent models is proposed as a good framework for deciding how to behave in such situations. Using longer playing horizons and experts that learn as they play, the regret-minimization framework can be extended to overcome several shortcomings of earlier approaches to the problem of multi-agent learning.

REFERENCES

• 1: P. Auer , N. Cesa-Bianchi , Y. Freund , R. E. Schapire, Gambling in a rigged casino: The adversarial multi-armed bandit problem, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.322, October 23-25, 1995
• 2: Chang, Y., & Kaelbling, L. P. (2001). Playing is believing: The role of beliefs in multi-agent learning. NIPS.
• 3: de Farias, D. P., & Meggido, N. (2004). How to combine expert (or novice) advice when actions impact the environment. Proceedings of NIPS.
• 4: Freund, Y., & Schapire, R. E. (1999). Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29, 79--103.
• 5: Fudenburg, D., & Levine, D. K. (1995). Consistency and cautious fictitious play. Journal of Economic Dynamics and Control, 19, 1065--1089.
• 6: Junling Hu , Michael P. Wellman, Multiagent Reinforcement Learning: Theoretical Framework and an Algorithm, Proceedings of the Fifteenth International Conference on Machine Learning, p.242-250, July 24-27, 1998
• 7: Michael J. Kearns , Satinder P. Singh, Near-Optimal Reinforcement Learning in Polynominal Time, Proceedings of the Fifteenth International Conference on Machine Learning, p.260-268, July 24-27, 1998
• 8: Littman, M. L. (1994). Markov games as a framework for multi-agent reinforcement learning. ICML.
• 9: Shie Mannor , Nahum Shimkin, Adaptive Strategies and Regret Minimization in Arbitrarily Varying Markov Environments, Proceedings of the 14th Annual Conference on Computational Learning Theory and and 5th European Conference on Computational Learning Theory, p.128-142, July 16-19, 2001
• 10: Nachbar, J., & Zame, W. (1996). Non-computable strategies and discounted repeated games. Economic Theory.