PREDICTION, LEARNING, AND GAMES

By WILLIAM MOORE

CONTENTS INTRODUCTION PREDICTION LEARNING GAMES A GENTLE START A NOTE TO THE READER PREDICTION WITH EXPERT ADVICE WEIGHTED AVERAGE PREDICTION AN OPTIMAL BOUND BOUNDS THAT HOLD UNIFORMLY OVER TIME AN IMPROVEMENT FOR SMALL LOSSES FORECASTERS USING THE GRADIENT OF THE LOSS SCALED LOSSES AND SIGNED GAMES THE MULTILINEAR FORECASTER THE EXPONENTIAL FORECASTER FOR SIGNED GAMES SIMULATABLE EXPERTS MINIMAX REGRET DISCOUNTED REGRET BIBLIOGRAPHIC REMARKS EXERCISES TIGHT BOUNDS FOR SPECI?C LOSSES FOLLOW THE BEST EXPERT EXP-CONCAVE LOSS FUNCTIONS THE GREEDY FORECASTER THE AGGREGATING FORECASTER MIXABILITY FOR CERTAIN LOSSES GENERAL LOWER BOUNDS RANDOMIZED PREDICTION WEIGHTED AVERAGE FORECASTERS FOLLOW THE PERTURBED LEADER INTERNAL REGRET CALIBRATION GENERALIZED REGRET CALIBRATION WITH CHECKING RULES EF?CIENT FORECASTERS FOR LARGE CLASSES OF EXPERTS TRACKING THE BEST EXPERT TREE EXPERTS THE SHORTEST PATH PROBLEM TRACKING THE BEST OF MANY ACTIONS PREDICTION WITH LIMITED FEEDBACK LABEL EF?CIENT PREDICTION LOWER BOUNDS PARTIAL MONITORING A GENERAL FORECASTER FOR PARTIAL MONITORING HANNAN CONSISTENCY AND PARTIAL MONITORING MULTI-ARMED BANDIT PROBLEMS AN IMPROVED BANDIT STRATEGY LOWER BOUNDS FOR THE BANDIT PROBLEM HOW TO SELECT THE BEST ACTION PREDICTION AND PLAYING GAMES GAMES AND EQUILIBRIA MINIMAX THEOREMS REPEATED TWO-PLAYER ZERO-SUM GAMES CORRELATED EQUILIBRIUM AND INTERNAL REGRET UNKNOWN GAMES: GAME-THEORETIC BANDITS CALIBRATION AND CORRELATED EQUILIBRIUM BLACKWELL’S APPROACHABILITY THEOREM POTENTIAL-BASED APPROACHABILITY CONVERGENCE TO NASH EQUILIBRIA CONVERGENCE IN UNKNOWN GAMES PLAYING AGAINST OPPONENTS THAT REACT ABSOLUTE LOSS OPTIMAL ALGORITHM FOR SIMULATABLE EXPERTS STATIC EXPERTS A SIMPLE EXAMPLE BOUNDS FOR CLASSES OF STATIC EXPERTS BOUNDS FOR GENERAL CLASSES LOGARITHMIC LOSS SEQUENTIAL PROBABILITY ASSIGNMENT MIXTURE FORECASTERS GAMBLING AND DATA COMPRESSION THE MINIMAX OPTIMAL FORECASTER EXAMPLES THE LAPLACE MIXTURE A RE?NED MIXTURE FORECASTER LOWER BOUNDS FOR MOST SEQUENCES PREDICTION WITH SIDE INFORMATION A GENERAL UPPER BOUND FURTHER EXAMPLES 10 SEQUENTIAL INVESTMENT PORTFOLIO SELECTION THE MINIMAX WEALTH RATIO PREDICTION AND INVESTMENT UNIVERSAL PORTFOLIOS THE EG INVESTMENT STRATEGY INVESTMENT WITH SIDE INFORMATION LINEAR PATTERN RECOGNITION BREGMAN DIVERGENCES POTENTIAL-BASED GRADIENT DESCENT THE TRANSFER FUNCTION FORECASTERS USING BREGMAN PROJECTIONS TIME-VARYING POTENTIALS THE ELLIPTIC POTENTIAL A NONLINEAR FORECASTER 11 10 MIXTURE FORECASTERS 11 11 BIBLIOGRAPHIC REMARKS 11 12 EXERCISES LINEAR CLASSI?CATION THE ZERO–ONE LOSS THE HINGE LOSS MAXIMUM MARGIN CLASSI?ERS LABEL EF?CIENT CLASSI?ERS KERNEL-BASED CLASSI?ERS REFERENCES