Share and Export
Share and Export
Kilian, Joe, Lang, Kevin J. and Pearlmutter, Barak A. (1994) Playing the Matching-Shoulders Lob-Pass Game with Logarithmic Regret. In: Proceedings of the seventh annual conference on Computational learning theory. Association for Computing Machinery (ACM), pp. 159-164. ISBN 0897916557
Preview
BP-Playing-1994.pdf
Download (161kB) | Preview
Abstract
The best previous algorithm for the matching shoulders lob-pass game, Abe and Takeuchi's (1993) ARTHUR, suffered O(t 1=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(log t) 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.
| Item Type: | Book Section |
|---|---|
| Keywords: | Matching-Shoulders Lob-Pass Game; Logarithmic Regret; algorithm; |
| Academic Unit: | Faculty of Science and Engineering > Computer Science |
| Item ID: | 8136 |
| Depositing User: | Barak Pearlmutter |
| Date Deposited: | 07 Apr 2017 15:35 |
| Publisher: | Association for Computing Machinery (ACM) |
| Refereed: | Yes |
| Related URLs: | |
| URI: | https://mural.maynoothuniversity.ie/id/eprint/8136 |
| Use Licence: | This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here |
Repository Staff Only (login required)
- Item control page
Downloads
Downloads per month over past year
