Archive for DIMACS workshop on Online Decision Algorithms

The goal of this web page is to archive documents from the DIMACS meeting on Online Decision Algorithms that took place during July 12 to July 15, 1999 in Rutgers University in New Jersey.

The order to the items corresponds to the chronological order in which the talks were given. I have the slides for some of the talks. In addition, I put some reference lists, pointers to home-pages and pointers to papers that are available electronically. Some of the slides were handwritten, so I had to scan them in. Those slides appear in the adobe acrobat format (pdf) and are rather large. The electronically generated slides are in postscript format.

There are many missing items. If you have taken part in the workshop and would like to contribute additional slides or other material, please Email it to me at

A similar workshop was held in the University of California in Santa Cruz in 1996. Some papers and slides were saved from that meeting. You can access that archive by clicking here

Best Regards
Yoav Freund

    Monday July 12, 1999

  1. A short guided tour in the land of online decision algorithms
    Yoav Freund, AT&T Labs-Research
    Home page

  2. Learning in Games
    Rakesh Vohra, Northwestern University
    Home page

  3. An overview of the competitive analysis of online algorithms and its relation to game theory
    Allan Borodin, University of Toronto and Ran El-Yaniv, The Technion, Israel
    Borodin's Home page
    El-Yaniv's Home page

  4. The Prequential Approach to Probability and Statistics
    Philip Dawid, University College London
    Slides (Handwritten 3Mb pdf)

  5. Decision Theory of Regret for Universal Coding, Gambling, and Prediction
    Andrew Barron, Yale University

  6. Reinforcement learning as a useful apporximation: accuracy of prediction in experimental games.
    Alvin Roth, Harvard University
    Home page

    Tuesday July 13, 1999

  7. Adaptive Srategies, Regret, and Approachability
    Sergiu Hart, Hebrew University, Jerusalem
    Paper: A General Class of Adaptive Strategies
    Paper: A Simple Adaptive Procedure Leading to Correlated Equilibrium
    Home page

  8. Information Geometry and its Applications
    Imre Csiszar, Hungarian Academy of Sciences
    Slides (handwritten - 1.6Mb pdf)
    Reference list

  9. Relative Loss Bounds for On-Line Learning Using Divergence Measures
    Manfred Warmuth, University of California - Santa Cruz
    Home page

  10. Learning to Play Games Using Multiplicative Weights
    Robert Schapire, AT&T Labs
    Paper:Adaptive game playing using multiplicative weights
    Paper: Gambling in a rigged casino: The adversarial multi-armed bandit problem
    Home page

  11. Worst-case analyses of the exploration/exploitation tradeoff
    Phil Long, National University of Singapore
    Reference List
    Home page

  12. Tracking the Best Predictor
    Mark Herbster, Royal Holloway University

    Wednesday July 14, 1999

  13. Rational Learning
    Ehud Kalai, Northwestern University
    Slides (handwritten 3.5 Mb pdf)
    Home page

  14. Rational Bayesian Learning in Repeated Games
    John Nachbar, Wash University, St. Louis

  15. "When rational learning fails"
    Dean Foster, Wharton School, University of Pennsylvania and Peyton Young,
    John Hopkins University

  16. `Impossibility' of Absolute Continuity
    Chris Sanchirrico, Columbia University

  17. Minimizing regret: the general case
    Aldo Rustichini, Tilburg University

  18. Reasonable Learning in Non-cooperative Games and the Internet
    Eric Friedman, Rutgers University, Department of Economics
    Home page

  19. Bayesian representations of stochastic processes under learning - De-Finetti revisited
    Matt Jackson, CalTech; Rann Smorodnitsky, Technion, and Ehud Kalai, Northwestern University

  20. Fast Universal Portfolios For Parameterized Target Classes
    Jason Cross, Yale University

  21. On-Line Learning and the Metrical Task System Problem
    Avrim Blum, Carnegie Mellon University
    Associated Paper: Avrim Blum and Carl Burch, On-line Learning and the Metrical Task System Problem.
    Proceedings of the 10th Annual Conference on Computational Learning Theory (COLT '97), pages 45--53. To appear in Machine Learning.
    Home page

  22. Choosing the best option under adversarial conditions
    Yossi Azar, Tel Aviv University
    Home page

  23. On prediction of individual sequences relative to a set of experts.
    N. Cesa-Bianchi, University of Milan, Italy and Gabor Lugosi,
    Pompeu Fabra University, Spain
    Cesa-Bianchi's home page
    Lugosi's home page

  24. Approachability in Infinite Dimensional Spaces and an Application:
    A Universal Algorithm for Generating Extended Normal Numbers
    Ehud Lehrer, Tel-Aviv University

  25. Calibration with Many Checking Rules
    Alvaro Sandroni, Northwestern University

  26. Average case and worst case sample complexity of learning distributions
    Manfred Opper, Sheffield University
    Home page

    Document last modified on August 5, 1999.