Multiarmed Bandit Algorithms Based on Empirical Moments

摘要

多腕バンディット問題は強化学習における知識の探索と活用のジレンマを定式化したもので，複数台のスロットマシンを選んでプレイするギャンブラーのモデルとして表される．本論文では各マシンからのrewardが区間［0，1］上の確率分布にしたがう場合を考える。このモデルにおいては理論限界を漸近的に達成する戦略が知られているが、これは経験分布そのものを用いた凸最適化を毎回実行する必要がある。そこで本研究では任意の次数dまでの経験モーメントのみを用いて計算可能な戦略を新たに提案し、その性能が次数dを増やすことで理論限界に漸近することを示す。また、提案戦略においてはモーメント制約付きKLダイバージュンス最小化を計算する必要があるが、これがTchebycheff systemの理論を用いることにより代数方程式系の求解に帰着できることを示す。%In the multiarmed bandit problem a gambler chooses an arm of a slot machine to pull considering a tradeoff between exploration and exploitation. We study the stochastic bandit problem where each arm has a reward distribution supported in a known bounded interval, e.g. [0,1]. For this model, there exists a policy which achieves the theoretical bound asymptotically. However the optimal policy requires a computation of a convex optimization which involves the empirical distribution of each arm. In this paper, we propose a policy which exploits the first d empirical moments for arbitrary d fixed in advance. The asymptotic upper bound of the regret of the policy approaches the theoretical bound as d increases. The proposed policy requires a minimization of KL divergence with moment constraints. We show by the theory of Tchebycheff system that the optimal value is obtained by solving polynomial equations.