REINFORCEMENT LEARNING

An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits

December 5, 2020

Abstract

In the contextual linear bandit setting, algorithms built on the optimism principle fail to exploit the structure of the problem and have been shown to be asymptotically suboptimal. In this paper, we follow recent approaches of deriving asymptotically optimal algorithms from problem-dependent regret lower bounds and we introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We build on a reformulation of the lower bound, where context distribution and exploration policy are decoupled, and we obtain an algorithm robust to unbalanced context distributions. Then, using an incremental primal-dual approach to solve the Lagrangian relaxation of the lower bound, we obtain a scalable and computationally efficient algorithm. Finally, we remove forced exploration and build on confidence intervals of the optimization problem to encourage a minimum level of exploration that is better adapted to the problem structure. We demonstrate the asymptotic optimality of our algorithm, while providing both problem-dependent and worst-case finite-time regret guarantees. Our bounds scale with the logarithm of the number of arms, thus avoiding the linear dependence common in all related prior works. Notably, we establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits. Finally, we verify that our algorithm obtains better empirical performance than state-of-the-art baselines.

Download the Paper

AUTHORS

Written by

Andrea Tirinzonin

Matteo Pirotta

Marcello Restelli

Alessandro Lazaric

Research Topics

Reinforcement Learning

Related Publications

May 03, 2019

RANKING & RECOMMENDATIONS

Multi-Perspective Relevance Matching with Hierarchical ConvNets for Social Media Search | Facebook AI Research

Despite substantial interest in applications of neural networks to information retrieval, neural ranking models have mostly been applied to “standard” ad hoc retrieval tasks over web pages and newswire articles. This paper proposes MP-HCNN…

Jinfeng Rao, Wei Yang, Yuhao Zhang, Ferhan Ture, Jimmy Lin

May 03, 2019

November 01, 2018

RANKING & RECOMMENDATIONS

Horizon: Facebook's Open Source Applied Reinforcement Learning Platform | Facebook AI Research

In this paper we present Horizon, Facebook’s open source applied reinforcement learning (RL) platform. Horizon is an end-to-end platform designed to solve industry applied RL problems where datasets are large (millions to billions of…

Jason Gauci, Edoardo Conti, Yitao Liang, Kittipat Virochsiri, Yuchen He, Zachary Kaden, Vivek Narayanan, Xiaohui Ye

November 01, 2018

December 03, 2018

RANKING & RECOMMENDATIONS

NLP

Training with Low-precision Embedding Tables | Facebook AI Research

Starting from the success of Glove and Word2Vec in natural language processing, continuous representations are widely deployed in many other domain of applications. These applications span over encoding textual information to modeling user and…

Jian Zhang, Jiyan Yang, Hector Yuen

December 03, 2018

December 18, 2020

RANKING & RECOMMENDATIONS

REINFORCEMENT LEARNING

Reinforcement Learning-based Product Delivery Frequency Control

Frequency control is an important problem in modern recommender systems. It dictates the delivery frequency of recommendations to maintain product quality and efficiency.…

Yang Liu, Zhengxing Chen, Kittipat Virochsiri, Juan Wang, Jiahao Wu, Feng Liang

December 18, 2020

Help Us Pioneer The Future of AI

We share our open source frameworks, tools, libraries, and models for everything from research exploration to large-scale production deployment.