Cornering Stationary and Restless Mixing Bandits with Remix-UCB
We study the restless bandit problem where arms are associated with stationary ϕ-mixing processes and where rewards are therefore dependent: the question that arises from this setting is that of carefully recovering some independence by 'ignoring' the values of some rewards. As we shall see, the bandit problem we tackle requires us to address the exploration/exploitation/independence trade-off, which we do by considering the idea of a waiting arm in the new Remix-UCB algorithm, a generalization of Improved-UCB for the problem at hand, that we introduce. We provide a regret analysis for this bandit strategy; two noticeable features of Remix-UCB are that i) it reduces to the regular Improved-UCB when the ϕ-mixing coefficients are all 0, i.e. when the i.i.d scenario is recovered, and ii) when ϕ(n) = O(n −α ), it is able to ensure a controlled regret of order Θ ∆ (α−2)/α * log 1/α T , where ∆ * encodes the distance between the best arm and the best suboptimal arm, even in the case when α < 1, i.e. the case when the ϕ-mixing coefficients are not summable.
Summary: The paper studies the problem of restless mixing bandits, more specifically the case when rewards of an arm evolve according to a \phi-mixing process. In this problem the rewards distribution of an arm is not stationary and evolves according to a \phi-mixing process where the correlation between rewards of an arm in two different rounds decrease over time. The paper proposes an algorithm called Remix-UCB (a variant of Improved-UCB for the stationary case). In this algorithm we maintain confidence bounds on rewards of each arm. Then we proceed in epochs and play each arm certain number of times before eliminating clearly suboptimal arm. The key new idea is that at the end of each of these epochs the algorithm decides to play the best arm certain number of rounds and not use information in these rounds to update confidence bounds. The paper shows regret bound of \theta( (\log T)^{1/\alpha} \delta^(\alpha-1)/alpha) with respect to bench mark of single best arm. Clarity: The paper is written in a reasonably clear manner. Significance of the problem: Restless bandits are an important class of bandit problems which model many interesting problems in machine learning on online problems. Any good result should be of interest to the community. Originality: Although the paper studies the classic problem of restless ucb, the specific variant has not been studied in the literature. This variant looks quite natural and should be of interest. The algorithm that the paper proposes is quite natural and borrows heavily on several techniques in the area including using confidence bounds to estimate mean reward and iterated prunning of suboptimal arms. But the paper also introduces a new idea of playing the best known arm without updating confidence bounds in their algorithm which makes sense in practice. Comments: The focus of the paper is on getting asymptotic regret which scales like a power of \log(T). If we wanted something of \sqrt{T} regret we can just use exp3 algorithm as the benchmark is single best arm. Main issues: - One of the interesting aspects of restless bandits is the fact that we can define stronger benchmarks which can play different arms in each round. So the fact that the paper competes against single best arm is a bit weak. - While it is true that we tend to ignore constant in regret bounds the paper is a bit too loose in regret analysis. It does not show dependence on parameters such as k.- technical correction \lambda_k^\tau = O(t^{3/4}) (line 236 and similarly line 262) - Improved UCB gives interesting bounds when \sum \phi < O(\sqrt{t}) and not just as \sum \phi < constant as the paper indicates.