Communication-Constrained Bandits under Additive Gaussian Noise
share
We study a distributed stochastic multi-armed bandit where a client supplies the learner with communication-constrained feedback based on the rewards for the corresponding arm pulls. In our setup, the client must encode the rewards such that the second moment of the encoded rewards is no more than P, and this encoded reward is further corrupted by additive Gaussian noise of variance σ^2; the learner only has access to this corrupted reward. For this setting, we derive an information-theoretic lower bound of Ω(√(KT/𝚂𝙽𝚁∧1)) on the minimax regret of any scheme, where 𝚂𝙽𝚁 := P/σ^2, and K and T are the number of arms and time horizon, respectively. Furthermore, we propose a multi-phase bandit algorithm, 𝚄𝙴-𝚄𝙲𝙱++, which matches this lower bound to a minor additive factor. 𝚄𝙴-𝚄𝙲𝙱++ performs uniform exploration in its initial phases and then utilizes the upper confidence bound (UCB) bandit algorithm in its final phase. An interesting feature of 𝚄𝙴-𝚄𝙲𝙱++ is that the coarser estimates of the mean rewards formed during a uniform exploration phase help to refine the encoding protocol in the next phase, leading to more accurate mean estimates of the rewards in the subsequent phase. This positive reinforcement cycle is critical to reducing the number of uniform exploration rounds and closely matching our lower bound.
READ FULL TEXT