Zheng Wen

Zheng Wen

Auto-generated profile, based on publicly available information

Zheng Wen

Stanford University Columbia University

Research Focus & Metrics

Academic Career Length

11Years (2016-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
12 July 2018 in Foundations and Trends in Machine Learning
Verified
Journal Article
Closed access
PDF file
DRDaniel J. Russo
Daniel J. Russo
BRBenjamin Van Roy
Benjamin Van Roy
AKAbbas Kazerouni
Abbas Kazerouni
IOIan Osband
Ian Osband
ZWZheng Wen
Zheng Wen
Thompson sampling is an algorithm for online decision problems where actions are taken sequentially in a manner that must balance between exploiting what is known to maximize immediate performance and investing to accumulate new information that may improve future performance. The algorithm addresses a broad range of problems in a computationally efficient manner and is therefore enjoying wide use. This tutorial covers the algorithm and its application, illustrating concepts through a range of examples, including Bernoulli bandit problems, shortest path problems, product recommendation, assortment, active learning with neural networks, and reinforcement learning in Markov decision processes. Most of these problems involve complex information structures, where information revealed by taking an action informs beliefs about other actions. We will also discuss when and why Thompson sampling is or is not effective and relations to alternative algorithms.

1 August 2017 in Mathematics of Operations Research
Verified
Journal Article
Closed access
ZWZheng Wen
Zheng Wen
BRBenjamin Van Roy
Benjamin Van Roy
We consider the problem of reinforcement learning over episodes of a finite-horizon deterministic system and as a solution propose optimistic constraint propagation (OCP), an algorithm designed to synthesize efficient exploration and value function generalization. We establish that when the true value function lies within a given hypothesis class, OCP selects optimal actions over all but at most D episodes, where D is the eluder dimension of the given hypothesis class. We establish further efficiency and asymptotic performance guarantees that apply even if the true value function does not lie in the given hypothesis class, for the special case where the hypothesis class is the span of prespecified indicator functions over disjoint sets. We also discuss the computational complexity of OCP and present computational results involving two illustrative examples.

29 May 2018 in arXiv
Verified
Preprint
Open access
PDF file
ALAlfonso Lobos
Alfonso Lobos
PGPaul Grigas
Paul Grigas
ZWZheng Wen
Zheng Wen
KLKuang-Chih Lee
Kuang-Chih Lee
We develop a novel optimization model to maximize the profit of a Demand-Side Platform (DSP) while ensuring that the budget utilization preferences of the DSP's advertiser clients are adequately met. Our model is highly flexible and can be applied in a Real-Time Bidding environment (RTB) with arbitrary auction types, e.g., both first and second price auctions. Our proposed formulation leads to a non-convex optimization problem due to the joint optimization over both impression allocation and bid price decisions. Using Fenchel duality theory, we construct a dual problem that is convex and can be solved efficiently to obtain feasible bidding prices and allocation variables that can be deployed in a RTB setting. With a few minimal additional assumptions on the properties of the auctions, we demonstrate theoretically that our computationally efficient procedure based on convex optimization principles is guaranteed to deliver a globally optimal solution. We conduct experiments using data from a real DSP to validate our theoretical findings and to demonstrate that our method successfully trades off between DSP profitability and budget utilization in a simulated online environment.

24 May 2018 in arXiv
Verified
Preprint
Open access
PDF file
SVSharan Vaswani
Sharan Vaswani
BKBranislav Kveton
Branislav Kveton
ZWZheng Wen
Zheng Wen
ARAnup Rao
Anup Rao
MSMark Schmidt
Mark Schmidt
YAYasin Abbasi-Yadkori
Yasin Abbasi-Yadkori
We investigate the use of bootstrapping in the bandit setting. We first show that the commonly used non-parametric bootstrapping (NPB) procedure can be provably inefficient and establish a near-linear lower bound on the regret incurred by it under the bandit model with Bernoulli rewards. We show that NPB with an appropriate amount of forced exploration can result in sub-linear albeit sub-optimal regret. As an alternative to NPB, we propose a weighted bootstrapping (WB) procedure. For Bernoulli rewards, WB with multiplicative exponential weights is mathematically equivalent to Thompson sampling (TS) and results in near-optimal regret bounds. Similarly, in the bandit setting with Gaussian rewards, we show that WB with additive Gaussian weights achieves near-optimal regret. Beyond these special cases, we show that WB leads to better empirical performance than TS for several reward distributions bounded on $[0,1]$. For the contextual bandit setting, we give practical guidelines that make bootstrapping simple and efficient to implement and result in good empirical performance on real-world datasets.

13 June 2018 in arXiv
Verified
Preprint
Open access
PDF file
SLShuai Li
Shuai Li
YAYasin Abbasi-Yadkori
Yasin Abbasi-Yadkori
BKBranislav Kveton
Branislav Kveton
SMS. Muthukrishnan
S. Muthukrishnan
VVVishwa Vinay
Vishwa Vinay
ZWZheng Wen
Zheng Wen
Many web systems rank and present a list of items to users, from recommender systems to search and advertising. An important problem in practice is to evaluate new ranking policies offline and optimize them before they are deployed. We address this problem by proposing evaluation algorithms for estimating the expected number of clicks on ranked lists from historical logged data. The existing algorithms are not guaranteed to be statistically efficient in our problem because the number of recommended lists can grow exponentially with their length. To overcome this challenge, we use models of user interaction with the list of items, the so-called click models, to construct estimators that learn statistically efficiently. We analyze our estimators and prove that they are more efficient than the estimators that do not use the structure of the click model, under the assumption that the click model holds. We evaluate our estimators in a series of experiments on a real-world dataset and show that they consistently outperform prior estimators.

31 May 2016 in arXiv
Verified
Preprint
Open access
PDF file
SKSumeet Katariya
Sumeet Katariya
BKBranislav Kveton
Branislav Kveton
CSCsaba Szepesvári
Csaba Szepesvári
ZWZheng Wen
Zheng Wen
A search engine recommends to the user a list of web pages. The user examines this list, from the first page to the last, and clicks on all attractive pages until the user is satisfied. This behavior of the user can be described by the dependent click model (DCM). We propose DCM bandits, an online learning variant of the DCM where the goal is to maximize the probability of recommending satisfactory items, such as web pages. The main challenge of our learning problem is that we do not observe which attractive item is satisfactory. We propose a computationally-efficient learning algorithm for solving our problem, dcmKL-UCB; derive gap-dependent upper bounds on its regret under reasonable assumptions; and also prove a matching lower bound up to logarithmic factors. We evaluate our algorithm on synthetic and real-world problems, and show that it performs well even when our model is misspecified. This work presents the first practical and regret-optimal online algorithm for learning to rank with multiple clicks in a cascade-like click model.