Prédiction randomisée de suites individuelles

 Access to full text

 Full (PDF)

1. [1] AUER P.(2002). Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3 :397-422. Zbl1084.68543MR1984023
2. [2] AUER P., CESA-BIANCHI N., FREUND Y. et SCHAPIRE R.(2002). The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32 :48-77. Zbl1029.68087MR1954855
3. [3] AUER P. et LONG P.M.(1999). Structural results for online learning models with and without queries. Machine Learning, 36 :147-181. Zbl0947.68080
4. [4] AWERBUCH B. et KLEINBERG R. D.(2004). Adaptive routing with end-to-end feedback : distributed learning and geometric approaches. In Proceedings of the 36th ACM Symposium on the Theory of Computing, pages 45-53. ACM Press. Zbl1192.68020MR2121584
5. [5] AZUMA K.(1967). Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, 68 :357-367. Zbl0178.21103MR221571
6. [6] BAÑOS A.(1968). On pseudo-games. Annals of Mathematical Statistics, 39 :1932-1945. Zbl0222.90056MR234560
7. [7] BERRY D.A. et FRISTEDT B.(1985). Bandit Problems. Chapman and Hall. Zbl0659.62086MR813698
8. [8] BLACKWELL D.(1956). An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6 :1-8. Zbl0074.34403MR81804
9. [9] BLACKWELL D.(1956). Controlled random walks. In Proceedings of the International Congress of Mathematicians, 1954, volume III, pages 336-338. North-Holland. Zbl0073.13204MR85141
10. [10] BOUSQUET O. et WARMUTH M.(2002). Tracking a small set of experts by mixing past posteriors. Journal of Machine Learning Research, 3 :363-396. Zbl1084.68552MR1984022
11. [11] CESA-BIANCHI N.(1999). Analysis of two gradient-based algorithms for on-line regression. Journal of Computer and System Sciences, 59(3) :392-411. Zbl0961.68148MR1726769
12. [12] CESA-BIANCHI N., FREUND Y., HAUSSLER D., HELMBOLD D.P., SCHAPIRE R. et WARMUTH M.(1997). How to use expert advice. Journal of the ACM, 44(3) :427-485. Zbl0890.68066MR1470152
13. [13] CESA-BIANCHI N. et LUGOSI G.(1999). On prediction of individual sequences. Annals of Statistics, 27 :1865-1895. Zbl0961.62081MR1765620
14. [14] CESA-BIANCHI N. et LUGOSI G.(2003). Potential-based algorithms in on-line prediction and game theory. Machine Learning, 51 :239-261. Zbl1026.68152
15. [15] CESA-BIANCHI N. et LUGOSI G.(2006). Prediction, Learning, and Games. Cambridge University Press, New York. Zbl1114.91001MR2409394
16. [16] CESA-BIANCHI N., LUGOSI G. et STOLTZ G.(2004). Minimizing regret with label efficient prediction. IEEE Transactions on Information Theory, 51 :2152-2162. Zbl1078.68693MR2235288
17. [17] CESA-BIANCHI N., LUGOSI G. et STOLTZ G.(2004). Regret minimization under partial monitoring. Prépublication DMA-04-18, Ecole normale supérieure, Paris. 
18. [18] COVER T.(1965). Behavior of sequential predictors of binary sequences. In Proceedings of the 4th Prague Conference on Information Theory, Statistical Decision Functions, Random Processes, pages 263-272. Maison d'édition de l'Académie des sciences de Tchécoslovaquie, Prague. MR217944
19. [19] FEDER M., MERHAV N. et GUTMAN M.(1992). Universal prediction of individual sequences. IEEE Transactions on Information Theory, 38 :1258-127. Zbl0775.94076MR1168747
20. [20] FOSTER D.(1991). Prediction in the worst-case. Annals of Statistics, 19 :1084-1090. Zbl0725.62085MR1105864
21. [21] FOSTER D. et VOHRA R.(1998). Asymptotic calibration. Biometrika, 85 :379-390. Zbl0947.62059MR1649119
22. [22] FOSTER D. et VOHRA R.(1999). Regret in the on-line decision problem. Games and Economic Behavior, 29 :7-36. Zbl0984.91025MR1729308
23. [23] FREEDMAN D.A.(1975). On tail probabilities for martingales. Annals of Probability, 3 :100-118. Zbl0313.60037MR380971
24. [24] FUDENBERG D. et LEVINE D.K.(1998). The Theory of Learning in Games. MIT Press. Zbl0939.91004MR1629477
25. [25] GITTINS J.C.(1989). Multi-Armed Bandit Allocation Indices. Wiley-lnterscience series in Systems and Optimization. Wiley. Zbl0699.90068MR996417
26. [26] GYÖRGY A., LINDER T. et LUGOSI G.(2004). Efficient algorithms and minimax bounds for zero-delay lossy source coding. IEEE Transactions on Signal Processing, 52 :2337-2347. 
27. [27] GYÖRGY A., LINDER T. et LUGOSI G.(2004). A "follow the perturbed leader"-type algorithm for zero-delay quantization of individual sequences. In Data Compression Conference, pages 342-351. 
28. [28] GYÖRGY A., LINDER T. et LUGOSI G.(2005). Tracking the best of many experts. In Proceedings of the 18th Annual Conference on Learning Theory, pages 204-216. Zbl1137.68540
29. [29] GYÖRGY A., LINDER T., LUGOSI G. et OTTUCSÂK Gy.(2005). The on-line shortest path bandit problem. Manuscrit. 
30. [30] HANNAN G.(1957). Approximation to Bayes risk in repeated play. Contributions to the theory of games, 3 :97-139. Zbl0078.32804
31. [31] HART S. et MAS-COLELL A.(2000). A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68 :1127-1150. Zbl1020.91003MR1779146
32. [32] HART S. et MAS-COLELL A.(2001) A general class of adaptive strategies. Journal of Economic Theory, 98 :26-54. Zbl0994.91007MR1832647
33. [33] HART S. et MAS-COLELL A.(2002). A reinforcement procedure leading to correlated equilibrium. In Economic Essays : A Festschrift for Werner Hildenbrand, pages 181-200. Springer. Zbl1023.91004MR1940643
34. [34] HAUSSLER D., KIVINEN J. et WARMUTH M.(1998). Sequential prediction of individual sequences under general loss functions. IEEE Transactions on Information Theory, 44 :1906-1925, 1998. Zbl1026.68579MR1664051
35. [35] HELMBOLD D.P., LITTLESTONE N. et LONG P.M.(2000). Apple tasting. Information and Computation, 161(2) :85-139. Zbl1045.68573MR1781564
36. [36] HELMBOLD D.P. et PANIZZA S.(1997). Some label efficient learning results. In Proceedings of the 10th Annual Conference on Computational Learning Theory, pages 218-230. ACM Press. 
37. [37] HELMBOLD D.P. et SCHAPIRE R.(1997). Predicting nearly as well as the best pruning of a decision tree. Machine Learning, 27(1) :51-68. 
38. [38] HELMBOLD D.P. et WARMUTH M.(1998). Tracking the best expert. Machine Learning, 32(2) :151-178. Zbl0912.68165
39. [39] HOEFFDING W.(1963). Probability inequalities for sums of bounded random variables. Journal ofthe American Statistical Association, 58 :13-30. Zbl0127.10602MR144363
40. [40] HUTTER M. et POLAND J.(2004). Prediction with expert advice by following the perturbed and penalized leader. Prépublication IDSIA-20-04, Istituto Dalle Molle di Studi sull'Tntelligenza Artificiale, Suisse. 
41. [41] KALAI A. et VEMPALA S.(2003). Efficient algorithms for the online decision problem. In Proceedings of the 16th Annual Conference on Learning Theory, pages 26-40. Springer. Zbl1274.91143
42. [42] LAI T.L. et ROBBINS H.(1985). Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6 :4-22. Zbl0568.62074MR776826
43. [43] LEMPEL A. et ZIV J.(1976). On the complexity of an individual sequence. IEEE Transactions on Information Theory, 22 :75-81. Zbl0337.94013MR389403
44. [44] LITTLESTONE N. et WARMUTH M.(1994). The weighted majority algorithm. Information and Computation, 108 :212-261. Zbl0804.68121MR1265851
45. [45] MANNOR S. et SHIMKIN N.(2003). On-line learning with imperfect monitoring. In Proceedings of the 16th Annual Conference on Learning Theory, pages 552-567. Springer. Zbl1274.91083
46. [46] McMAHAN H. B. et BLUM A.(2004). Online geometric optimization in the bandit setting against an adaptive adversary. In Proceedings of the 17th Annual Conference on Learning Theory, pages 109-123. Springer, 2004. Zbl1078.68128MR2177904
47. [47] MEGIDDO N.(1980). On repeated games with incomplete information played by non-Bayesian players. International Journal of Game Theory, 9 :157-167. Zbl0441.90118MR595967
48. [48] MERHAV N. et FEDER M.(1993). Universal schemes for sequential decision from individual data sequences. IEEE Transactions on Information Theory, 39.1280-1292. Zbl0801.94012MR1267158
49. [49] MERHAV N. et FEDER M.(1998). Universal prediction. IEEE Transactions on Information Theory, 44 :2124-2147. Zbl0933.94008MR1658815
50. [50] MERTENS J.-F., SORIN S. et ZAMIR S.(1994). Repeated games. core Discussion paper, numéros 9420, 9421, 9422, Louvain-la-Neuve, Belgique. 
51. [51] NEVEU J.(1975). Discrete Parameter Martingales. North-Holland. Zbl0345.60026MR402915
52. [52] PICCOLBONI A. et SCHINDELHAUER C.(2001). Discrete prediction games with arbitrary feedback and loss. In Proceedings of the 14th Annual Conference on Computational Learning Theory, pages 208-223. Zbl0992.68506MR2042037
53. [53] ROBBINS H.(1952). Some aspects of the sequential design of experiments. Bullettin of the American Mathematical Society, 55 :527-535. Zbl0049.37009MR50246
54. [54] RUSTICHINI A.(1999). Minimizing regret : The general case. Games and Economic Behavior, 29 :224-243. Zbl0954.91011MR1729318
55. [55] STOLTZ G.(2005). Information incomplète et regret interne en prédiction de suites individuelles. Thèse de doctorat, Université Paris-Sud, Orsay. 
56. [56] TAKIMOTO E. et WARMUTH M.(2004). Path kernels and multiplicative updates. Journal of Machine Learning Research, 4 :773-818. Zbl1083.68592MR2075997
57. [57] VOVK V.(1990). Aggregating strategies. In Proceedings of the 3rd Annual Workshop on Computational Learning Theory, pages 372-383. 
58. [58] VOVK V.(1998). A game of prediction with expert advice. Journal of Computer and System Sciences, 56 :153-173. Zbl0945.68528MR1629690
59. [59] VOVK V.(1999). Derandomizing stochastic prediction strategies. Machine Learning, 35 :247-282. Zbl0941.68128
60. [60] VOVK V.(2001). Competitive on-line statistics. International Statistical Review, 69 :213-248. Zbl1211.62200
61. [61] WEISSMAN T. et MERHAV N.(2001). Universal prediction of binary individual sequences in the presence of noise. IEEE Transactions on Information Theory, 47 :2151-2173. Zbl1016.94017MR1873194
62. [62] WEISSMAN T., MERHAV N. et SOMEKH-BARUCH(2001). Twofold universal prediction schemes for achieving the finite state predictability of a noisy individual binary sequence. IEEE Transactions on Information Theory, 47 :1849-1866. Zbl1051.62523MR1842523
63. [63] ZIV J.(1978). Coding theorems for individual sequences. IEEE Transactions on Information Theory, 24 :405-412. Zbl0416.94006MR504371
64. [64] ZIV J.(1980). Distortion-rate theory for individual sequences. IEEE Transactions on Information Theory, 26 :137-143. Zbl0431.94030MR570318
65. [65] ZIV J. et LEMPEL A.(1977). A universal algorithm for sequential data-compression. IEEE Transactions on Information Theory, 23 :337-343. Zbl0379.94010MR530215

1. Alexandre B. Tsybakov, Agrégation d’estimateurs et optimisation stochastique