Efficient methods in counterfactual policy learning and sequential decision making
Méthodes efficaces en apprentissage contrefactuel de politiques et prise de décisions séquentielles
Résumé
Because logged data has become ubiquitous in wide-range applications and since onlineexploration may be sensitive, counterfactual methods have gained significant attention inthe recent decade. Such data comes in the form of an observationaldataset where partial feedback information is associated to context covariates and actionstaken by a logging decision policy. The aim of counterfactual policy methods is then tolearn a policy that improves upon the logging policy; it is often termed as offline contextualbandits. While many applications require a discrete action setting, less attention has beengiven to continuous action spaces that are however widespread in online auction problems. In that sense, developing algorithms with guarantees that work wellin these practical settings, as well as enlarging benchmark datasets represents an importantresearch direction that has been a focus of this thesis. We introduce subsequently a methodfor continuous action policies along with a new CoCoA benchmark dataset. Moreover, weinvestigate the use of optimization approaches related to the counterfactual risk minimizationlearning objective function and propose a novel estimator that is more amenable to gradientbased optimization.Likewise, counterfactual learning methods typically use inverse propensity scoring estimators that are prone to variance issues. The latter is even more pronounced in cases where the past decisions underexplored the action space. As such, an offline analysis may not suffice to undertake statistically plausible decisions; collecting additional data to increase the sample size may be necessary. In that sense, sequential designs of adaptively collected data should allow to improve the performance of counterfactual policy learning in terms of convergence guarantees and in practical settings. We investigate this direction in this thesis by proposing a novel estimator with improved variance-dependent convergence guarantees which in turn allow to obtain fast rates under an assumption that is similar to restart strategies in accelerated optimization methods.Conversely, when online exploration is possible, a rich literature has been built to design effective online policies in contextual bandits. In that case,the Optimistim in the Face of Uncertainty Learning (OFUL) principle has been instrumental in obtaining algorithms with sublinear regret rates and especially practical performances. While seminal methods use linear assumptions on the form of the reward, nonlinear embeddings of kernel methods provide richer representations of the data that allow forcontrolled regret guarantees and improved performances in applications. However, suchkernel methods suffer from scalability issues as they become computationally intensive whenthe number of decision steps increases. As such, we investigate in this thesis the use ofkernel approximation methods inthis contextual bandit task to derive an efficient implementation of the Kernel UCB method. We analyze the regret and explicit in which kernel approximation regimes we manage to restore the original regret rate while obtaining faster computations.Eventually, in sequential learning, an agent can be called to choose betweenarms in a set of alternatives and thereof develop a randomized strategy in adversarial settings. However, in some applications the learner has to choose between a large number of alternatives that many possess inherent similarities which may be implied by closely correlated losses. In that case, a naive learning agent may sufferunnecessary regret and conversely, an agent that would benefit from side information on asimilarity structure may obtain improved performances. This thesis brings contributionswith regards to a class of adversarial multi-armed bandit problems with a novel algorithm onlearning with expert advices and a nested exponential weights algorithms that performs alayered exploration of the learner’s nested set of alternatives.
Les données "loggées" sont devenues omniprésentes dans de nombreuses applications. Ces données observationnelles contiennent des informations partielles associées à des variables contextuelles et aux actions prises par une politique initiale. Le but de ces méthodes d’apprentissage contrefactuel en "bandits contextuels hors ligne" est d’apprendre une politique qui améliore la politique initiale. Bien que de nombreuses applications nécessitent un espace d’action discret, un intérêt moindre a été accordé aux méthodes avec actions continues. Aussi, le développement d’algorithmes avec des garanties théoriques qui fonctionnent dans ces régimes, ainsi que l’élargissement des données de référence en source ouverte est une direction de recherche importante qui a été un objet de cette thèse. Nous y présentons une méthode pour actions continues ainsi qu’un nouveau jeu de données CoCoA. De plus, nous étudions l’utilisation de méthodes d’optimisation liées à la nature de la fonction objective du minimisation de risque contrefactuel et proposons un nouvel estimateur qui est plus adapté à l’optimisation basée sur des gradients.Par ailleurs, les méthodes d’apprentissage contrefactuel utilisent généralement des estimateurs de pondération de propension inverse qui sont sujets à des problèmes de variance. Ce dernier est encore plus prononcé dans les cas où les décisions passées ont sous-exploré l’espace d’action. Par conséquent, une analyse hors ligne peut ne pas suffire pour prendre des décisions statistiquement plausibles ; il peut être nécessaire de collecter des données supplémentaires pour augmenter la taille d’échantillon. Ainsi, les conceptions séquentielles de collection de données de manière adaptative devraient permettre d’améliorer les garanties de convergence. Nous explorons cette direction dans cette thèse en proposant un nouvel estimateur avec des garanties améliorées qui permettent à leur tour d’obtenir des taux rapides sous une hypothèse similaire à celle des stratégies de redémarrage dans les méthodes d’optimisation accélérée.Inversement, lorsque l’exploration en ligne est possible, le principe d’optimisme a été déterminant pour obtenir des algorithmes avec des taux de regret sous-linéaires et des performances particulièrement remarquables dans des problèmes pratiques. Alors que les premières méthodes supposaient des hypothèses de linéarité sur la forme de la fonction de coût, les représentations non linéaires des méthodes à noyau permettent d’obtenir des représentations de données plus riches avec des performances améliorées. Cependant, de telles méthodes à noyau souffrent de problèmes de scalabilité car elles deviennent couteuses en calcul lorsque le nombre d’étapes de décision augmente. Nous étudions dans cette thèse l’utilisation de méthodes d’approximations pour proposer une implémentation efficace de la méthode UCB à noyau. Nous analysons le regret et explicitons les régimes dans lesquels l’approximation des méthodes à noyau permet de restaurer le taux de regret original tout en obtenant des calculs plus rapides.Enfin, en apprentissage séquentiel, un agent peut être appelé à choisir entre des actions dans un ensemble d’alternatives et développer une stratégie aléatoire dans des environnements adversariaux. Cependant, dans certaines applications, l’apprenant doit choisir entre un grand nombre d’alternatives qui présentent des similarités pouvant être induites par des coûts corrélées. Dans ce cas, un agent d’apprentissage peut souffrir d’un regret inutile et inversement, un agent qui bénéficierait d’informations annexes sur une structure de similarité devrait obtenir des performances améliorées. Cette thèse apporte des contributions sur des classes de problèmes de bandits multi-bras adversariaux avec un nouvel algorithme d’apprentissage avec conseils d’experts et un algorithme de poids exponentiel emboîté qui effectue une exploration en couches de l’espace d'actions.
Origine : Version validée par le jury (STAR)