Past Seminars - Spring 2022

Adaptivity and Confounding in Multi-Armed Bandit Experiments

Authors: Chao Qin, Daniel Russo

Abstract: We explore a new model of bandit experiments where a potentially nonstationary sequence of contexts influences arms' performance. Context-unaware algorithms risk confounding while those that perform correct inference face information delays. Our main insight is that an algorithm we call deconfounted Thompson sampling strikes a delicate balance between adaptivity and robustness. Its adaptivity leads to optimal efficiency properties in easy stationary instances, but it displays surprising resilience in hard nonstationary ones which cause other adaptive algorithms to fail.

Speaker Bio: Daniel joined the Decision, Risk, and Operations division of the Columbia Business School in Summer 2017. Daniels research lies at the intersection of statistical machine learning and online decision making, mostly falling under the broad umbrella of reinforcement learning. Outside academia, Daniel works with Spotify to apply reinforcement learning style models to audio recommendations.

Prior to joining Columbia, Daniel spent one great year as an assistant professor in the MEDS department at Northwestern's Kellogg School of Management and one year at Microsoft Research in New England as Postdoctoral Researcher. Daniel recieved his PhD from Stanford University in 2015, where he was advised by Benjamin Van Roy. In 2011 he recieved a BS in Mathematics and Economics from the University of Michigan.

Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability

Authors: Aadirupa Saha, Akshay Krishnamurthy

Abstract: We study the K-armed contextual dueling bandit problem, a sequential decision making setting in which the learner uses contextual information to make two decisions, but only observes \emph{preference-based feedback} suggesting that one decision was better than the other. We focus on the regret minimization problem under realizability, where the feedback is generated by a pairwise preference matrix that is well-specified by a given function class . We provide a new algorithm that achieves the optimal regret rate for a new notion of best response regret, which is a strictly stronger performance measure than those considered in prior works. The algorithm is also computationally efficient, running in polynomial time assuming access to an online oracle for square loss regression over . This resolves an open problem of Dudík et al. [2015] on oracle efficient, regret-optimal algorithms for contextual dueling bandits.

Speaker Bio: Aadirupa is a postdoctoral researcher at Microsoft Research New York City. She obtained her PhD from the department of Computer Science, Indian Institute of Science, Bangalore, advised by Aditya Gopalan and Chiranjib Bhattacharyya. Aadirupa was an intern at Microsoft Research, Bangalore, Inria, Paris, and Google AI, Mountain View. Aadirupas research interests include Bandits, Reinforcement Learning, Optimization, Learning theory, Algorithms.

Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approach

Authors: Xuezhou Zhang, Yuda Song, Masatoshi Uehara, Mengdi Wang, Alekh Agarwal, Wen Sun

Abstract: We present BRIEE (Block-structured Representation learning with Interleaved Explore Exploit), an algorithm for efficient reinforcement learning in Markov Decision Processes with block-structured dynamics (i.e., Block MDPs), where rich observations are generated from a set of unknown latent states. BRIEE interleaves latent states discovery, exploration, and exploitation together, and can provably learn a near-optimal policy with sample complexity scaling polynomially in the number of latent states, actions, and the time horizon, with no dependence on the size of the potentially infinite observation space. Empirically, we show that BRIEE is more sample efficient than the state-of-art Block MDP algorithm HOMER and other empirical RL baselines on challenging rich-observation combination lock problems that require deep exploration.

Speaker Bio: Xuezhou Zhang is currently an Associate Research Scholar in the Department of Electrical and Computer Engineering at Princeton University, working with Mengdi Wang. He received his Ph.D. in Computer Sciences from the University of Wisconsin-Madison in 2021, advised by Jerry Zhu. Prior to that, he obtained his B.S. in Applied Mathematics from UCLA in 2016. He is a visitor at Simons Institute for the Theory of Computing in Spring 2022. His research primarily focuses on reinforcement learning theory and applications.

Representation Learning for Online and Offline RL in Low-rank MDPs

Authors: Masatoshi Uehara, Xuezhou Zhang, Wen Sun

Abstract: This work studies the question of Representation Learning in RL: how can we learn a compact low-dimensional representation such that on top of the representation we can perform RL procedures such as exploration and exploitation, in a sample efficient manner. We focus on the low-rank Markov Decision Processes (MDPs) where the transition dynamics correspond to a low-rank transition matrix. Unlike prior works that assume the representation is known (e.g., linear MDPs), here we need to learn the representation for the low-rank MDP. We study both the online RL and offline RL settings. For the online setting, operating with the same computational oracles used in FLAMBE (Agarwal et al), the state-of-art algorithm for learning representations in low-rank MDPs, we propose an algorithm REP-UCB Upper Confidence Bound driven Representation learning for RL), which significantly improves the sample complexity from O˜(A^9d^7/(ϵ^10(1−γ)^22)) for FLAMBE to O˜(A^2d^4/(ϵ^2(1−γ)^5)) with d being the rank of the transition matrix (or dimension of the ground truth representation), A being the number of actions, and γ being the discounted factor. Notably, REP-UCB is simpler than FLAMBE, as it directly balances the interplay between representation learning, exploration, and exploitation, while FLAMBE is an explore-then-commit style approach and has to perform reward-free exploration step-by-step forward in time. For the offline RL setting, we develop an algorithm that leverages pessimism to learn under a partial coverage condition: our algorithm is able to compete against any policy as long as it is covered by the offline distribution.

Speaker Bio: Masatoshi is a PhD student at Cornell in computer science department. Previously, he was a PhD student at Harvard in statistics department. Masatoshi is interested in statistical learning theory and method for sequential decision making. In particular, his interests are reinforcement learning, causal inference, online learning and application to e-commerce. Masatoshi is advised by Nathan Kallus (Cornell). 

Sample complexity for average-reward MDP

Authors: Dylan J. Foster, Sham M. Kakade, Jian Qian, Alexander Rakhlin

Abstract: A fundamental challenge in interactive learning and decision making, ranging from bandit problems to reinforcement learning, is to provide sample-efficient, adaptive learning algorithms that achieve near-optimal regret. This question is analogous to the classical problem of optimal (supervised) statistical learning, where there are well-known complexity measures (e.g., VC dimension and Rademacher complexity) that govern the statistical complexity of learning. However, characterizing the statistical complexity of interactive learning is substantially more challenging due to the adaptive nature of the problem. The main result of this work provides a complexity measure, the Decision-Estimation Coefficient, that is proven to be both necessary and sufficient for sample-efficient interactive learning. In particular, we provide:

1. a lower bound on the optimal regret for any interactive decision making problem, establishing the Decision-Estimation Coefficient as a fundamental limit.

2. a unified algorithm design principle, Estimation-to-Decisions (E2D), which transforms any algorithm for supervised estimation into an online algorithm for decision making. E2D attains a regret bound matching our lower bound, thereby achieving optimal sample-efficient learning as characterized by the Decision-Estimation Coefficient.

Taken together, these results constitute a theory of learnability for interactive decision making. When applied to reinforcement learning settings, the Decision-Estimation Coefficient recovers essentially all existing hardness results and lower bounds. More broadly, the approach can be viewed as a decision-theoretic analogue of the classical Le Cam theory of statistical estimation; it also unifies a number of existing approaches -- both Bayesian and frequentist.

Speaker Bio: Dylan is a senior researcher at Microsoft Research, New England, where he is a member of the Reinforcement Learning Group. Previously, Dylan was a postdoctoral fellow at the MIT Institute for Foundations of Data Science, and prior to this he received his PhD from the Department of Computer Science at Cornell University (2019), advised by Karthik Sridharan. Dylan received my BS and MS in electrical engineering from the University of Southern California in 2014. He works on theory for machine learning. Dylans research lies at the intersection of machine learning and decision making, including data-driven reinforcement learning and control, contextual bandits, and statistical learning in causal/counterfactual settings. He is interested in uncovering new algorithmic principles and fundamental limits for data-driven decision making, with themes including: Sample efficiency, Algorithm design, and Adaptivity. 

Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning

Authors: Tong Zhang

Abstract: Thompson Sampling has been widely used for contextual bandit problems due to the flexibility of its modeling power. However, a general theory for this class of methods in the frequentist setting is still lacking. In this paper, we present a theoretical analysis of Thompson Sampling, with a focus on frequentist regret bounds. In this setting, we show that the standard Thompson Sampling is not aggressive enough in exploring new actions, leading to suboptimality in some pessimistic situations. A simple modification called Feel-Good Thompson Sampling, which favors high reward models more aggressively than the standard Thompson Sampling, is proposed to remedy this problem. We show that the theoretical framework can be used to derive Bayesian regret bounds for standard Thompson Sampling, and frequentist regret bounds for Feel-Good Thompson Sampling. It is shown that in both cases, we can reduce the bandit regret problem to online least squares regression estimation. For the frequentist analysis, the online least squares regression bound can be directly obtained using online aggregation techniques which have been well studied. The resulting bandit regret bound matches the minimax lower bound in the finite action case. Moreover, the analysis can be generalized to handle a class of linearly embeddable contextual bandit problems (which generalizes the popular linear contextual bandit model). The obtained result again matches the minimax lower bound. Finally we illustrate that the analysis can be extended to handle some MDP problems.

Speaker Bio: Tong Zhang is a professor of Computer Science and Mathematics at The Hong Kong University of Science and Technology. Previously, he was a professor at Rutgers university, and worked at IBM, Yahoo, Baidu, and Tencent. Tong Zhang's research interests include machine learning algorithms and theory, statistical methods for big data and their applications. He is a fellow of ASA, IEEE, and IMS, and he has been in the editorial boards of leading machine learning journals and program committees of top machine learning conferences. Tong Zhang received a B.A. in mathematics and computer science from Cornell University and a Ph.D. in Computer Science from Stanford University.

The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning

Authors: Vivek Borkar, Shuhang Chen, Adithya Devraj, Ioannis Kontoyiannis, Sean Meyn

Abstract: The paper concerns convergence and asymptotic statistics for stochastic approximation driven by Markovian noise: θ_{n+1}=θ_n+α_{n+1}f(θ_n,Φ_{n+1}),n≥0, in which each θ_n∈ℜ^d, {Φ_n} is a Markov chain on a general state space X with stationary distribution π, and f:ℜ^d×X→ℜ^d. In addition to standard Lipschitz bounds on f, and conditions on the vanishing step-size sequence {α_n}, it is assumed that the associated ODE is globally asymptotically stable with stationary point denoted θ*, where f¯(θ)=E[f(θ,Φ)] with Φ∼π. Moreover, the ODE@∞ defined with respect to the vector field, f¯∞(θ):=lim_{r→∞}r^{−1}f¯(rθ),θ∈ℜ^d, is asymptotically stable. The main contributions are summarized as follows:

(i) The sequence θ is convergent if Φ is geometrically ergodic, and subject to compatible bounds on f.

The remaining results are established under a stronger assumption on the Markov chain: A slightly weaker version of the Donsker-Varadhan Lyapunov drift condition known as (DV3).

(ii) A Lyapunov function is constructed for the joint process {θ_n,Φ_n} that implies convergence of {θ_n} in L4.

(iii) A functional CLT is established, as well as the usual one-dimensional CLT for the normalized error zn:=(θ_n−θ*)/\sqrt{α_n}. Moment bounds combined with the CLT imply convergence of the normalized covariance, lim_{n→∞}E[z_nz^T_n]=Σ_θ, where Σ_θ is the asymptotic covariance appearing in the CLT.

(iv) An example is provided where the Markov chain Φ is geometrically ergodic but it does not satisfy (DV3). While the algorithm is convergent, the second moment is unbounded.

Speaker Bio: Dr. Sean Meyn received the B.A. degree in mathematics from the University of California, Los Angeles (UCLA), in 1982 and the Ph.D. degree in electrical engineering from McGill University, Canada, in 1987 (with Prof. P. Caines, McGill University).  He is now Professor and Robert C. Pittman Eminent Scholar Chair in the Department of Electrical and Computer Engineering at the University of Florida,  the director of the Laboratory for Cognition & Control, and director of the Florida Institute for Sustainable Energy. His academic research interests include theory and applications of decision and control, stochastic processes, and optimization.  He has received many awards for his research on these topics, and is a fellow of the IEEE.