Playing the matching-shoulders lob-pass game with logarithmic regret

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.

REFERENCES

• 1: Naoki Abe , Jun-ichi Takeuchi, The “lob-pass” problem and an on-line learning model of rational choice, Proceedings of the sixth annual conference on Computational learning theory, p.422-428, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168389]
• 2: Ryan S. Borgstrom , S. Rao Kosaraju, Comparison-based search in the presence of errors, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.130-136, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167129]
• 3: Herrnstein, R. (1990). Rational Choice Theory. Amerzcan Psychologist, ~5(3), 356-367.
• 4: 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.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Theory, Verification