@article{JSFS_2006__147_1_5_0, author = {Lugosi, G\'abor}, title = {Pr\'ediction randomis\'ee de suites individuelles}, journal = {Journal de la Soci\'et\'e fran\c{c}aise de statistique}, pages = {5--37}, publisher = {Soci\'et\'e fran\c{c}aise de statistique}, volume = {147}, number = {1}, year = {2006}, language = {fr}, url = {http://www.numdam.org/item/JSFS_2006__147_1_5_0/} }
TY - JOUR AU - Lugosi, Gábor TI - Prédiction randomisée de suites individuelles JO - Journal de la Société française de statistique PY - 2006 SP - 5 EP - 37 VL - 147 IS - 1 PB - Société française de statistique UR - http://www.numdam.org/item/JSFS_2006__147_1_5_0/ LA - fr ID - JSFS_2006__147_1_5_0 ER -
Lugosi, Gábor. Prédiction randomisée de suites individuelles. Journal de la Société française de statistique, Tome 147 (2006) no. 1, pp. 5-37. http://www.numdam.org/item/JSFS_2006__147_1_5_0/
[1] Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3 :397-422. | MR | Zbl
(2002).[2] The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32 :48-77. | MR | Zbl
, , et (2002).[3] Structural results for online learning models with and without queries. Machine Learning, 36 :147-181. | Zbl
et (1999).[4] 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. | MR | Zbl
et (2004).[5] Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, 68 :357-367. | MR | Zbl
(1967).[6] On pseudo-games. Annals of Mathematical Statistics, 39 :1932-1945. | MR | Zbl
(1968).[7] Bandit Problems. Chapman and Hall. | MR
et (1985).[8] An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6 :1-8. | MR | Zbl
(1956).[9] Controlled random walks. In Proceedings of the International Congress of Mathematicians, 1954, volume III, pages 336-338. North-Holland. | MR | Zbl
(1956).[10] Tracking a small set of experts by mixing past posteriors. Journal of Machine Learning Research, 3 :363-396. | MR | Zbl
et (2002).[11] Analysis of two gradient-based algorithms for on-line regression. Journal of Computer and System Sciences, 59(3) :392-411. | MR | Zbl
(1999).[12] How to use expert advice. Journal of the ACM, 44(3) :427-485. | MR | Zbl
, , , , et (1997).[13] On prediction of individual sequences. Annals of Statistics, 27 :1865-1895. | MR | Zbl
et (1999).[14] Potential-based algorithms in on-line prediction and game theory. Machine Learning, 51 :239-261. | Zbl
et (2003).[15] Prediction, Learning, and Games. Cambridge University Press, New York. | MR | Zbl
et (2006).[16] Minimizing regret with label efficient prediction. IEEE Transactions on Information Theory, 51 :2152-2162. | MR | Zbl
, et (2004).[17] Regret minimization under partial monitoring. Prépublication DMA-04-18, Ecole normale supérieure, Paris.
, et (2004).[18] 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. | MR
(1965).[19] Universal prediction of individual sequences. IEEE Transactions on Information Theory, 38 :1258-127. | MR | Zbl
, et (1992).[20] Prediction in the worst-case. Annals of Statistics, 19 :1084-1090. | MR | Zbl
(1991).[21] Asymptotic calibration. Biometrika, 85 :379-390. | MR | Zbl
et (1998).[22] Regret in the on-line decision problem. Games and Economic Behavior, 29 :7-36. | MR | Zbl
et (1999).[23] On tail probabilities for martingales. Annals of Probability, 3 :100-118. | MR | Zbl
(1975).[24] The Theory of Learning in Games. MIT Press. | MR | Zbl
et (1998).[25] Multi-Armed Bandit Allocation Indices. Wiley-lnterscience series in Systems and Optimization. Wiley. | MR | Zbl
(1989).[26] Efficient algorithms and minimax bounds for zero-delay lossy source coding. IEEE Transactions on Signal Processing, 52 :2337-2347.
, et (2004).[27] A "follow the perturbed leader"-type algorithm for zero-delay quantization of individual sequences. In Data Compression Conference, pages 342-351.
, et (2004).[28] Tracking the best of many experts. In Proceedings of the 18th Annual Conference on Learning Theory, pages 204-216. | Zbl
, et (2005).[29] The on-line shortest path bandit problem. Manuscrit.
, , et (2005).[30] Approximation to Bayes risk in repeated play. Contributions to the theory of games, 3 :97-139. | Zbl
(1957).[31] A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68 :1127-1150. | MR | Zbl
et (2000).[32] A general class of adaptive strategies. Journal of Economic Theory, 98 :26-54. | MR | Zbl
et (2001)[33] A reinforcement procedure leading to correlated equilibrium. In Economic Essays : A Festschrift for Werner Hildenbrand, pages 181-200. Springer. | MR | Zbl
et (2002).[34] Sequential prediction of individual sequences under general loss functions. IEEE Transactions on Information Theory, 44 :1906-1925, 1998. | MR | Zbl
, et (1998).[35] Apple tasting. Information and Computation, 161(2) :85-139. | MR | Zbl
, et (2000).[36] Some label efficient learning results. In Proceedings of the 10th Annual Conference on Computational Learning Theory, pages 218-230. ACM Press.
et (1997).[37] Predicting nearly as well as the best pruning of a decision tree. Machine Learning, 27(1) :51-68.
et (1997).[38] Tracking the best expert. Machine Learning, 32(2) :151-178. | Zbl
et (1998).[39] Probability inequalities for sums of bounded random variables. Journal ofthe American Statistical Association, 58 :13-30. | MR | Zbl
(1963).[40] 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.
et (2004).[41] Efficient algorithms for the online decision problem. In Proceedings of the 16th Annual Conference on Learning Theory, pages 26-40. Springer.
et (2003).[42] Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6 :4-22. | MR | Zbl
et (1985).[43] On the complexity of an individual sequence. IEEE Transactions on Information Theory, 22 :75-81. | MR | Zbl
et (1976).[44] The weighted majority algorithm. Information and Computation, 108 :212-261. | MR | Zbl
et (1994).[45] On-line learning with imperfect monitoring. In Proceedings of the 16th Annual Conference on Learning Theory, pages 552-567. Springer. | Zbl
et (2003).[46] 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. | MR | Zbl
et (2004).[47] On repeated games with incomplete information played by non-Bayesian players. International Journal of Game Theory, 9 :157-167. | MR | Zbl
(1980).[48] Universal schemes for sequential decision from individual data sequences. IEEE Transactions on Information Theory, 39.1280-1292. | MR | Zbl
et (1993).[49] Universal prediction. IEEE Transactions on Information Theory, 44 :2124-2147. | MR | Zbl
et (1998).[50] Repeated games. core Discussion paper, numéros 9420, 9421, 9422, Louvain-la-Neuve, Belgique.
, et (1994).[51] Discrete Parameter Martingales. North-Holland. | MR
(1975).[52] Discrete prediction games with arbitrary feedback and loss. In Proceedings of the 14th Annual Conference on Computational Learning Theory, pages 208-223. | MR | Zbl
et (2001).[53] Some aspects of the sequential design of experiments. Bullettin of the American Mathematical Society, 55 :527-535. | MR | Zbl
(1952).[54] Minimizing regret : The general case. Games and Economic Behavior, 29 :224-243. | MR | Zbl
(1999).[55] Information incomplète et regret interne en prédiction de suites individuelles. Thèse de doctorat, Université Paris-Sud, Orsay.
(2005).[56] Path kernels and multiplicative updates. Journal of Machine Learning Research, 4 :773-818. | MR | Zbl
et (2004).[57] Aggregating strategies. In Proceedings of the 3rd Annual Workshop on Computational Learning Theory, pages 372-383.
(1990).[58] A game of prediction with expert advice. Journal of Computer and System Sciences, 56 :153-173. | MR | Zbl
(1998).[59] Derandomizing stochastic prediction strategies. Machine Learning, 35 :247-282. | Zbl
(1999).[60] Competitive on-line statistics. International Statistical Review, 69 :213-248. | Zbl
(2001).[61] Universal prediction of binary individual sequences in the presence of noise. IEEE Transactions on Information Theory, 47 :2151-2173. | MR | Zbl
et (2001).[62] Twofold universal prediction schemes for achieving the finite state predictability of a noisy individual binary sequence. IEEE Transactions on Information Theory, 47 :1849-1866. | MR | Zbl
, et (2001).[63] Coding theorems for individual sequences. IEEE Transactions on Information Theory, 24 :405-412. | MR | Zbl
(1978).[64] Distortion-rate theory for individual sequences. IEEE Transactions on Information Theory, 26 :137-143. | MR | Zbl
(1980).[65] A universal algorithm for sequential data-compression. IEEE Transactions on Information Theory, 23 :337-343. | MR | Zbl
et (1977).