On a Non-asymptotic Analysis Using Large Deviation Principles in the Multiarmed Bandit Problem

摘要

多腕バンデイツト問題は強化学習における知識の探索と活用のジレンマを定式化したもので,複数台のスロットマシンを選んでプレイするギャンブラーのモデルとして表される.本論文では各マシンからの報酬が区間[0,1]上の確率分布にしたがう場合をまず考える.このモデルにおいて理論限界を達成するものとしてDMED戦略が近年提案されたが,その評価は渐近論に大きく依存しており有限試行回数での性能評価は知られていない.そこで本研究ではKLダイパージエンスの挙動に関する漸近形でない大偏差原理を導出することによりDMED戦略の有限試行回数での性能評価を行ラ.さらに,報酬の分布のサポートが下側が非有界の場合であっても積率母関数が存在する場合には理論限界を達成可能であることを合わせて示す.%In reinforcement learning a tradeoff between exploration and exploitation is considered. Multiarmed bandit problems formulate this dilemma as a model of a gambler playing a slot machine with multiple arms. In this paper we first consider a stochastic bandit such that each arm has a reward distribution supported in a known interval, e.g., [0,1]. Recently a policy, DMED, is proposed and proved to achieve the asymptotic bound for the model. However, the derived regret bound is described in an asymptotic form and the performance in finite time has been unknown. We inspect this policy and derive a finite-time regret bound by refining large deviation probabilities to a simple finite form. Further, this observation reveals that the assumption on the lower-boundedness of the support is not essential and can be replaced with a weaker one, the existence of the moment generating function.