ABSTRACT
The best previous algorithm for the matching shoulders lob-pass game, ARTHUR (Abe and Takeuchi 1993), suffered O(t1/2) regret. We prove that this is the best possible performance for any algorithm that works by accurately estimating the opponent's payoff lines. Then we describe an algorithm which beats that bound and meets the information-theoretic lower bound of O(logt) regret by converging to the best lob rate without accurately estimating the payoff lines. The noise-tolerant binary search procedure that we develop is of independent interest.
- Abe, N. and Takeuchi, J. (1993). The lob-pass problem and an on-line learning model of rational choice. In Workshop on Computatwnal Learning Theory, pp. 422-428. Google ScholarDigital Library
- Borgstrom, R. S. and Kosaraju, S. R. (1993). Comp~rieon-B~sed Search in the Pre~ence of Errors. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pp. 130-136. Google ScholarDigital Library
- Herrnstein, R. (1990). Rational Choice Theory. Amerzcan Psychologist, ~5(3), 356-367.Google Scholar
- Rivest, R., Meyer, A., Kleitman, D., Winklmann, K., and Spencer, J. (1980). Coping with errors in binary search procedures. Journal of Computer and System Sciences, 33, 85-94.Google Scholar
Index Terms
- Playing the matching-shoulders lob-pass game with logarithmic regret
Recommendations
Playing against no-regret players
AbstractWe consider n-player repeated games where one optimizer plays against no-regret players. In a 2-player game, the optimizer can always guarantee an expected average utility of at least the Stackelberg value per round. However, if there are several ...
Toward General Mathematical Game Playing Agents
2018 IEEE Conference on Computational Intelligence and Games (CIG)General game playing AI and general video game playing AI are both active research areas. Mathematical games, like prisoner’s dilemma, rock-paper-scissors, or the snowdrift game can also be played by general purpose agents. An agent representation ...
Comments