7 papers · 1 filter
Universal Dynamic Portfolios
Yu-Jie Zhang, Yu-Xiang Wang, Peng Zhao +1
Cover's Universal Portfolio (Cover, 1991) matches the performance of the best constant rebalanced portfolio in hindsight. We generalize this framework to compete with an arbitrary…
Near-Optimal Regret in Adversarial Kernel Bandits
Yu-Jie Zhang, Hao Qiu, Jonathan Scarlett +1
We study the adversarial kernel bandit problem, in which the loss at each round is induced by an arbitrary bounded element of a reproducing kernel Hilbert space (RKHS). We propose…
On the Power of Adaptivity for -Best Arm Identification in Linear Bandits
Arnab Maiti, Yunbei Xu, Kevin Jamieson
We study the minimax sample complexity of -best arm identification in linear bandits. Given a compact action set that spans and an unknown…
Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback
Shinji Ito, Kevin Jamieson, Haipeng Luo +2
We study online learning in finite-horizon episodic Markov decision processes (MDPs) under the challenging aggregate bandit feedback model, where the learner observes only the cumu…
On the Universal Near Optimality of Hedge in Combinatorial Settings
Zhiyuan Fan, Arnab Maiti, Kevin Jamieson +2
In this paper, we study the classical Hedge algorithm in combinatorial settings. In each round, the learner selects a vector from a set ,…
Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries
Arnab Maiti, Zhiyuan Fan, Kevin Jamieson +2
In this paper, we study the online shortest path problem in directed acyclic graphs (DAGs) under bandit feedback against an adaptive adversary. Given a DAG with a sour…
Near-Optimal Pure Exploration in Matrix Games: A Generalization of Stochastic Bandits & Dueling Bandits
Arnab Maiti, Ross Boczar, Kevin Jamieson +1
We study the sample complexity of identifying the pure strategy Nash equilibrium (PSNE) in a two-player zero-sum matrix game with noise. Formally, we are given a stochastic model w…