砂包装メカニズムに基づいた追い越し方法：なぜ楽観的な価値関数は、マルチアームの盗賊問題で最適なソリューションを見つけるのですか？

マルチアームのBanditの問題は、ランダムな報酬を生成する複数のスロットマシン間で学習エージェントが最適なアームを選択する必要がある検索問題です。UCBアルゴリズムは、マルチアームの盗賊問題を解決するための最も人気のある方法の1つです。探索と搾取のバランスを調整することにより、対数後悔のパフォーマンスを実現します。UCBアルゴリズム以来、研究者は、楽観的な価値関数がマルチアームの盗賊問題で良いパフォーマンスを示すことを経験的に知っています。楽観的または楽観主義という用語は、価値関数が報酬のサンプル平均よりも十分に大きいことを示唆するかもしれません。UCBアルゴリズムの最初の定義は、後悔の最適化に焦点を当てており、値関数の楽観主義に直接基づいていません。私たちは、楽観主義が複数の武装したバンディットの問題で良いパフォーマンスを引き出す理由を考える必要があります。現在の記事では、マルチアームの盗賊問題を解決するために、追い越し方法と呼ばれる新しい方法を提案します。提案された方法の値関数は、報酬の期待値の推定器に関する信頼区間の上限として定義されます。値関数は、上限からの報酬の期待値に漸近的にアプローチします。値関数が漸近の下の期待値よりも大きい場合、学習エージェントは最適なアームを取得できるとほぼ確実です。この構造は、砂糖メカニズムと呼ばれます。これは、最適ではないアームの値関数の再成長がありません。つまり、学習エージェントは、各タイムステップで現在の最高のアームのみを演奏できることを意味します。その結果、提案された方法は高精度と低い後悔を達成し、それのいくつかの価値関数はUCBアルゴリズムを上回る可能性があります。この研究は、最も単純なフレームワークの1つによって、不確実な環境におけるエージェントの楽観主義の利点を示唆しています。

A multi-armed bandit problem is a search problem on which a learning agent must select the optimal arm among multiple slot machines generating random rewards. UCB algorithm is one of the most popular methods to solve multi-armed bandit problems. It achieves logarithmic regret performance by coordinating balance between exploration and exploitation. Since UCB algorithms, researchers have empirically known that optimistic value functions exhibit good performance in multi-armed bandit problems. The terms optimistic or optimism might suggest that the value function is sufficiently larger than the sample mean of rewards. The first definition of UCB algorithm is focused on the optimization of regret, and it is not directly based on the optimism of a value function. We need to think the reason why the optimism derives good performance in multi-armed bandit problems. In the present article, we propose a new method, which is called Overtaking method, to solve multi-armed bandit problems. The value function of the proposed method is defined as an upper bound of a confidence interval with respect to an estimator of expected value of reward: the value function asymptotically approaches to the expected value of reward from the upper bound. If the value function is larger than the expected value under the asymptote, then the learning agent is almost sure to be able to obtain the optimal arm. This structure is called sand-sifter mechanism, which has no regrowth of value function of suboptimal arms. It means that the learning agent can play only the current best arm in each time step. Consequently the proposed method achieves high accuracy rate and low regret and some value functions of it can outperform UCB algorithms. This study suggests the advantage of optimism of agents in uncertain environment by one of the simplest frameworks.