5 papers
Bicausal Optimal Transport for Markov Chains via Dynamic Programming
Vrettos Moulos
In this paper we study the bicausal optimal transport problem for Markov chains, an optimal transport formulation suitable for stochastic processes which takes into consideration t…
Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards
Vrettos Moulos
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 thi…
A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Bandits
Vrettos Moulos
This paper develops a Hoeffding inequality for the partial sums , where is an irreducible Markov chain on a finite state sp…
Optimal Best Markovian Arm Identification with Fixed Confidence
Vrettos Moulos
We give a complete characterization of the sampling complexity of best Markovian arm identification in one-parameter Markovian bandit models. We derive instance specific nonasympto…
Optimal Chernoff and Hoeffding Bounds for Finite State Markov Chains
Vrettos Moulos, Venkat Anantharam
This paper develops an optimal Chernoff type bound for the probabilities of large deviations of sums where is a real-valued function and $(X_k)_{k \in \m…