Individual sequence prediction—upper bounds and application for complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Individual sequence prediction—upper bounds and application for complexity

Full text

Pdf (999 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the twelfth annual conference on Computational learning theory table of contents

Santa Cruz, California, United States

Pages: 233 - 242

Year of Publication: 1999

ISBN:1-58113-167-4

Author

Chamy Allenberg

School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
Univ. of California, : University of California at Santa Cruz

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 19, Citation Count: 1

Additional Information:

references cited by index terms

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/307400.307446 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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	Alfredo Bafios. On pseudo-games. The Annals of Mathematical Statistics, 39(6): 1932-1945, 1968,
	3	Nicolò Cesa-Bianchi , Yoav Freund , David P. Helmbold , David Haussler , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.382-391, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167198]
	4	Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
	5	Amos Fiat , Dean P. Foster , Howard Karloff , Yuval Rabani , Yiftach Ravid , Sundar Vishwanathan, Competitive algorithms for layered graph traversal, Proceedings of the 32nd annual symposium on Foundations of computer science, p.288-297, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185381]
	6	Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Proceedings of the Second European Conference on Computational Learning Theory, p.23-37, March 13-15, 1995
	7	J. C. Gittins. Multi-armed Bandit Allocation Indices. John Wiley and Sons, 1989.
	8	T. Ishikida , P. Varaiya, Multi-armed bandit problem revisited, Journal of Optimization Theory and Applications, v.83 n.1, p.113-154, Oct. 1994 [doi>10.1007/BF02191765]
	9	T.L. Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6:4-22, 1985.
	10	Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
	11	N. Megiddo. On repeated games with incomplete information played by non-Bayesian players. International Journal of Game Theory, 9(3):157-167, 1980.
	12	H. Robbins. Some aspects of the sequential design of experiments. Bulletin American Mathematical Society, 55:527-535, 1952.
	13	Volodimir G. Vovk, Aggregating strategies, Proceedings of the third annual workshop on Computational learning theory, p.371-386, August 06-08, 1990, Rochester, New York, United States
	14	A. C. Yao. Probabilistic computation: towards a uniform measure of complexity. In 18th FOCS, pages 222-227, 1977
	15	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990