{"id":69,"date":"2016-10-21T12:57:01","date_gmt":"2016-10-21T10:57:01","guid":{"rendered":"http:\/\/project.inria.fr\/badass\/?page_id=69"},"modified":"2020-11-28T10:19:30","modified_gmt":"2020-11-28T09:19:30","slug":"publication","status":"publish","type":"page","link":"https:\/\/project.inria.fr\/badass\/publication\/","title":{"rendered":"Publications"},"content":{"rendered":"
The following works have been supported by the French Agence Nationale de la Recherche (ANR), under grant ANR-16- CE40-0002 (project BADASS).<\/div>\n
<\/div>\n
Please take a look at this link on HaL<\/a> for a complete list of publications.<\/div>\n

(WP3)<\/span> Monte-Carlo Tree Search by Best Arm Identification, <\/strong>E. Kaufmann<\/a>\u00a0<\/span> W. Koolen<\/a><\/span> in NIPS 2017 – 31st Annual Conference on Neural Information Processing Systems<\/i>, Dec 2017, Long Beach, United States.<\/span> HaL<\/a>
\n\u00abRecent advances in bandit tools and techniques for sequential learning are steadily enabling new applications and are promising the resolution of a range of challenging related problems. We study the game tree search problem, where the goal is to quickly identify the optimal move in a given game tree by sequentially sampling its stochastic payoffs. We develop new algorithms for trees of arbitrary depth, that operate by summarizing all deeper levels of the tree into confidence intervals at depth one, and applying a best arm identification procedure at the root. We prove new sample complexity guarantees with a refined dependence on the problem instance. We show experimentally that our algorithms outperform existing elimination-based algorithms and match previous special-purpose methods for depth-two trees.\u00bb<\/em><\/span><\/p>\n

(WP2)<\/span> Multi-Armed Bandit Learning in IoT Networks: Learning helps even in non-stationary settings<\/strong>, R. Bonnefoi<\/a> <\/span> L. Besson<\/a>\u00a0<\/span> C. Moy<\/a>\u00a0<\/span> E. Kaufmann<\/a>\u00a0<\/span> J. Palicot<\/a> <\/span> in CROWNCOM 2017 – 12th EAI International Conference on Cognitive Radio Oriented Wireless Networks<\/i>, Sep 2017, Lisbon, Portugal. HaL<\/a><\/span>
\n\u00abLa mise en place des futurs r\u00e9seaux Internet des Objets (IoT) n\u00e9cessitera de supporter de plus en plus d’appareils communicants. Nous prouvons que les objets adaptatifs, dans des bandes non licenci\u00e9es, peuvent utiliser les algorithmes d’apprentissage de type Bandit Multi-Bras (MAB) pour am\u00e9liorer l’exploitation des ressources. Nous \u00e9valuons les performances de deux algorithmes classiques d’apprentissage MAB, UCB1 et Thompson Sampling, pour prendre en charge la prise de d\u00e9cision d\u00e9centralis\u00e9e d’Analyse de Spectre, appliqu\u00e9e aux r\u00e9seaux IoT, ainsi que les performances d’apprentissage avec un nombre croissant d’objets intelligents. Nous montrons que l’utilisation d’algorithmes d’apprentissage aide \u00e0 adapter un plus grand nombre de dispositifs dans de tels r\u00e9seaux, m\u00eame lorsque tous les appareils finaux sont intelligents et changent de canal de fa\u00e7on dynamique. Dans le sc\u00e9nario \u00e9tudi\u00e9, l’apprentissage stochastique (MAB) fournit un gain allant jusqu’\u00e0 16% en terme de probabilit\u00e9s de transmission r\u00e9ussie, et a des performances quasi optimales m\u00eame dans les situations non stationnaires et non i.i.d. avec une majorit\u00e9 d’appareils intelligents.\u00bb<\/em><\/span><\/p>\n

(WP2)<\/span> Efficient tracking of a growing number of experts<\/strong>, J. Mourtada, O.-A. Maillard in Algorithmic Learning Theory (ALT), 2017.<\/span>
\n\u00abWe consider a variation on the problem of prediction with expert advice, where new forecasters that were unknown until then may appear at each round. As often in prediction with expert advice, designing an algorithm that achieves near-optimal regret guarantees is straightforward, using aggregation of experts. However, when the comparison class is sufficiently rich, for instance when the best expert and the set of experts itself change over time, such strategies require to maintain a prohibitive number of weights (typically exponential with the time horizon). By contrast, designing strategies that both achieve a near-optimal regret and maintain a reasonable number of weights is highly non-trivial. We consider three increasingly challenging objectives (simple regret, shifting regret and sparse shifting regret) that extend existing notions defined for a fixed expert ensemble; in each case, we design strategies that achieve tight regret bounds, adaptive to the parameters of the comparison class, while being computationally inexpensive. Moreover, our algorithms are anytime, agnostic to the number of incoming experts and completely parameter-free. Such remarkable results are made possible thanks to two simple but highly effective recipes: first the \u201cabstention trick\u201d that comes from the specialist framework and enables to handle the least challenging notions of regret, but is limited when addressing more sophisticated objectives. Second, the \u201cmuting trick\u201d that we introduce to give more flexibility. We show how to combine these two tricks in order to handle the most challenging class of comparison strategies.\u00bb<\/em><\/span><\/p>\n

(WP1)<\/span> Boundary Crossing Probabilities for General Exponential Families<\/strong>, O.-A. Maillard in Algorithmic Learning Theory (ALT), 2017<\/span>. ArXiv<\/a>.
\n\u00abWe consider parametric exponential families of dimension K<\/span><\/span><\/span><\/span> on the real line. We study a variant of \\textit{boundary crossing probabilities} coming from the multi-armed bandit literature, in the case when the real-valued distributions form an exponential family of dimension K<\/span><\/span><\/span><\/span>. Formally, our result is a concentration inequality that bounds the probability that B^<\/span><\/span><\/span>\u03c8<\/span><\/span>(<\/span>\u03b8<\/span>^<\/span><\/span><\/span><\/span>n<\/span><\/span>,<\/span>\u03b8<\/span>\u22c6<\/span><\/span>)<\/span>\u2265<\/span>f<\/span>(<\/span>t<\/span>\/<\/span><\/span><\/span>n<\/span>)<\/span>\/<\/span><\/span><\/span>n<\/span><\/span><\/span><\/span>, where \u03b8<\/span>\u22c6<\/span><\/span><\/span><\/span><\/span> is the parameter of an unknown target distribution, \u03b8<\/span>^<\/span><\/span><\/span><\/span>n<\/span><\/span><\/span><\/span><\/span> is the empirical parameter estimate built from n<\/span><\/span><\/span><\/span> observations, \u03c8<\/span><\/span><\/span><\/span> is the log-partition function of the exponential family and B<\/span><\/span><\/span>\u03c8<\/span><\/span><\/span><\/span><\/span> is the corresponding Bregman divergence. From the perspective of stochastic multi-armed bandits, we pay special attention to the case when the boundary function f<\/span><\/span><\/span><\/span> is logarithmic, as it is enables to analyze the regret of the state-of-the-art KL-UCB and KL-UCB+ strategies, whose analysis was left open in such generality. Indeed, previous results only hold for the case when K<\/span>=<\/span>1<\/span><\/span><\/span><\/span>, while we provide results for arbitrary finite dimension K<\/span><\/span><\/span><\/span>, thus considerably extending the existing results. Perhaps surprisingly, we highlight that the proof techniques to achieve these strong results already existed three decades ago in the work of T.L. Lai, and were apparently forgotten in the bandit community. We provide a modern rewriting of these beautiful techniques that we believe are useful beyond the application to stochastic multi-armed bandits.\u00bb<\/em><\/span><\/p>\n

(WP3)<\/span> Spectral Learning from a Single Trajectory under Finite-State Policies<\/strong>, B. Balle, O.-A. Maillard in International conference on Machine Learning, 2017<\/span>.
\n\u00ab<\/em><\/span>We present spectral methods of moments for <\/em>learning sequential models from a single trajectory, <\/em>in stark contrast with the classical literature <\/em>that assumes the availability of multiple i.i.d. <\/em><\/span>trajectories. Our approach leverages an efficient<\/em> SVD-based learning algorithm for weighted automata <\/em>and provides the first rigorous analysis <\/em>for learning many important models using dependent<\/em> data. We state and analyze the algorithm under <\/em>three increasingly difficult scenarios: probabilistic <\/em>automata, stochastic weighted automata, <\/em>and reactive predictive state representations controlled<\/em> by a finite-state policy. Our proofs include <\/em>novel tools for studying mixing properties <\/em>of stochastic weighted automata.<\/em><\/span> \u00bb<\/em><\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

The following works have been supported by the French Agence Nationale de la Recherche (ANR), under grant ANR-16- CE40-0002 (project BADASS). Please take a look at this link on HaL for a complete list of publications. (WP3) Monte-Carlo Tree Search by Best Arm Identification, E. Kaufmann\u00a0 W. Koolen in NIPS\u2026<\/p>\n

Continue reading<\/span><\/i><\/a> <\/p>\n","protected":false},"author":950,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-69","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/project.inria.fr\/badass\/wp-json\/wp\/v2\/pages\/69","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/project.inria.fr\/badass\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/project.inria.fr\/badass\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/project.inria.fr\/badass\/wp-json\/wp\/v2\/users\/950"}],"replies":[{"embeddable":true,"href":"https:\/\/project.inria.fr\/badass\/wp-json\/wp\/v2\/comments?post=69"}],"version-history":[{"count":15,"href":"https:\/\/project.inria.fr\/badass\/wp-json\/wp\/v2\/pages\/69\/revisions"}],"predecessor-version":[{"id":194,"href":"https:\/\/project.inria.fr\/badass\/wp-json\/wp\/v2\/pages\/69\/revisions\/194"}],"wp:attachment":[{"href":"https:\/\/project.inria.fr\/badass\/wp-json\/wp\/v2\/media?parent=69"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}