Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards
We study an extension of the classic stochastic multi-armed bandit problem which involves multiple plays and Markovian rewards in the rested bandits setting. In order to tackle this problem we consider an adaptive allocation rule which at each stage combines the information from the sample means of all the arms, with the Kullback-Leibler upper confidence bound of a single arm which is selected in round-robin way. For rewards generated from a one-parameter exponential family of Markov chains, we provide a finite-time upper bound for the regret incurred from this adaptive allocation rule, which reveals the logarithmic dependence of the regret on the time horizon, and which is asymptotically optimal. For our analysis we devise several concentration results for Markov chains, including a maximal inequality for Markov chains, that may be of interest in their own right. As a byproduct of our analysis we also establish asymptotically optimal, finite-time guarantees for the case of multiple plays, and i.i.d. rewards drawn from a one-parameter exponential family of probability densities. Additionally, we provide simulation results that illustrate that calculating Kullback-Leibler upper confidence bounds in a round-robin way, is significantly more efficient than calculating them for every arm at each round, and that the expected regrets of those two approaches behave similarly.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Exponential convergence rate for Iterative Markovian Fitting
We consider the discrete-time Schrödinger bridge problem on a finite state space. Although it has been known that the Iterative Markovian Fitting (IMF) algorithm converges in Kullback-Leibler divergence to the ground tru…
Hyperfinite Construction of $G$-expectation
The hyperfinite $G$-expectation is a nonstandard discrete analogue of $G$-expectation (in the sense of Robinsonian nonstandard analysis). A lifting of a continuous-time $G$-expectation operator is defined as a hyperfinit…
Information-Theoretic Approach for Model Reduction Over Finite Time Horizon
This paper presents an information-theoretic approach for model reduction for finite time simulation. Although system models are typically used for simulation over a finite time, most of the metrics (and pseudo-metrics) …
A solvable generative model with a linear, one-step denoiser
We develop an analytically tractable single-step diffusion model based on a linear denoiser and present explicit formula for the Kullback-Leibler divergence between generated and sampling distribution, taken to be isotro…
MemorizationOnline Convex Optimization with Sublinear Noisy Probes
We study Online Convex Optimization (OCO) over a convex set $K\subseteq \mathbb R^d$, where in each round $t$ the learner selects $x_t\in K$ and then observes a convex loss $f_t:K\to[0,1]$, with the goal of minimizing re…