The key observation is that there is an evolving body of knowledge that leads to statements that remind us of probabilistic statements yet which apply to* all *sequences, or at least those that satisfy certain *calibration properties. *

For example, the Limpel-Ziv algorithm stands ready to tell us about any sequence at all*. *On the other hand, Shafer-Vovk theory and Foster-Vohra theory make assumptions and draw conclusions which --- although not always overtly probabilistic --- still capture probabilistic effects. There are also connections to on-line learning, learning in games, competitive algorithms, self-orgainizing list, and perhaps too much more.

At first it seems useful to cast a wide net. This is the taxonomical step, which will probably lead to focusing on a subset of what we turn up.The next step might be to write a piece for the *Monthly *or the *Mathematical Inteligencer* that would exposit one of the manageable sub-themes. The broad hope is that this might be a theme that can be pursued to a considerable length.

- Fudenberg and Levine,
*Learning in Games* - Economics and Game Theory (David Levine's Site)
- Papers of Payton Young (who has a book that is scheduled to appear)
- Papers of Dean P. Foster
- Papers of Ehud Lehrer
- Papers of Nicolo Cesa-Bianchi
- Web Page of Michel Kearns
- Papers of Gabor Lugosi
- Stoltz, G. and Lugosi, G (2004) "Internal Regret in On-line Portfolio Selection"
- Papers of Sham Kakade

On Prediction of Individual Sequences by Cesa-Bianchi and Lugosi. The authors are well informed with the theory of probability inequalities. They seem to have pushed many of the "CS level" results into their final form. This is a benchmark paper.

Yohav Freund's Home Page and his many nice papers.

Schapire's Home Page and his many nice papers.

- Web page on Universal Portfolio Theory
- Papers of Tom Cover
- Kalai, Adam.and Vempala, Samtosh, "Efficient Algorithms for Universal Portfolios"
- Papers of Adam Kalai (including "Follow the leader for online optimization," which Kalai calls a "vesion of the one above" but which looks much different ---and cooler!).

- Adam Kalai's course at Chicago
- Avrim Blum's course at CMU
- Blum, Avrim, "On-Line Algorithms in Machine Learning" (survey)
- Allan Borodin and Ran El-Yaniv,
*Online Computation and Competitive Analysis*. Cambridge University Press - Martin Zinkevich's papers. The paper On-line Convex Programming and Generalized Infinitesimal Gradient Ascent sounds a little ponderous, but this paper is GREAT and beautifully written. You can use it to do in a systematic way many things which in the past required substantial ad hoc cleverness. This is a leap-frog paper.

- Shafer and Vovk, Probability and Finance: It's Only a Game!
- Papers of Shafer and Vovk

- Limpel-Ziv Web Site
- Papers of Adi Wyner (He'll soon remove the litte A-hats)

- Tom Furguson's home page has many relevant "selection" papers as well as an electronic book on optimal stopping.
- There is an extensive literature on Bandit problems, where in the simplest case one make draws from iid device A or iid device B. The goal is to maximize discounted total winnning from sequential play.
- Martin Zinkevich's method for on-line convex programs gives a new approach to bandit problems and the famous Gittins index.
- Other Gittens whizzes: Richard Weber, Bob Vanderbei, Avi Mandelbaum, Nick Frangos, Peter Whittle, and Robert Dalang.
- Berry
**,**Donald and Bert Fristedt (1985). Bandit Problems: Sequential Allocation of Experiments. London: Chapman and Hall. This is unfortunately out of print, but Don Berry kindly provided me a hard copy which I can share if you are interested. - Who was Gittens? Was the famous paper Gittens and James? Why is James not mentioned these days?

- Dimitri Bertsekas has many resources related to dynamic programming.
- Encyclopedia article on Stochastic Scheduling.
- José Niño-Mora's home page

Economics and Search, Hal Varian

- Ester Sammuel-Cahn (best proof of Sucheston's inequality)...in Tom Ferguson's electronic book.
- Optimal sequential selection of a monotone sequence from a random sample, (with S. Samuels), A
*nnals of Probability*, 9 (1981), 937--947.

- Robbins and Lai seem to have written the definative bandit paper.

- David Blackwell does not have an active web page, so I have begun to "archive" some of Blackwell's work on "sequence theory."
- Hannan (1957). This paper disappeared for a while from the collective consciousness, but now it is widely cited --- even though it is still almost impossible to find. Well, thanks to Rick Vohra, here it is in all of its untypset glory. Rumor has it that Hannan once said something like, "I am pleased to hear that people are now refering to my paper, but why do they only mention the results from one section?" My guess is that the idea of that section got passed around, but very few people took the time to find the full paper. Now every one has full and easy access. Blessings on the Web.

- Petersen, Karl. Ergodic Theory, Cambridge University Press, 1989.

- Bibiliography on Learning in Economics and in Games (Douglas Nelson, Tulane)
- Bibliography for Theory of Learning in Games

- Kolmogorov Complexity (Donoho?)
- Computable Languages, Halting Problem, Godel Numbers, etc.
- Evolutionary Algorithms
- Genetic Algorithms
- Jeez... almost everything, boosting etc.
- even My Old Non-random Sequence Papers
- Related Ideas for Exploration