基本の内容

各種定式化

この本の著者である東京大学の本多淳也先生のスライドを参照。つまるところ簡単なバンディット問題は...

アームを引いた後に得られる報酬の性質
- 確率的
- 敵対的
- 定常・非定常（アームの確率分布は時間につれて少しずつ変化していく）
目的関数
- 引いたアームすべてから得られる報酬の和の最大化
- 期待値がもっとも高いアームの判定（をなるべく少ない回数で決める）
その他の拡張
- linear bandit
- matroid bandit
- contextual bandit
- etc ...

のような分類があって、多分検索してすぐに出てくるのは確率的で期待値がもっとも高いアームの判定をするものが多い印象?

Exploration/Exploitation Dilemma

Deepmindの方の講義映像を下の記事にてリンク。もっとも単純には。いくつかランダムに探索した後で常にもっとも良かったアームばかり引いていては最適なアームを見つけられない。一方で、常に探索しているだけだと損失が大きくなってしまうということ。

paper.hatenadiary.jp

Stationary Problem(定常なケース)

Action-Value Methods

Richard Sutton 氏による資料。

web: 2.2 Action-Value Methods

行動選択の戦略

greedy(貪欲)

最も単純だけどそれなりに強い。過去の経験から最も良かったアームを常に選択する。

ε-Greedy

貪欲な戦略だと最適解でないのにアームを引き続ける可能性があるから、εの確率でランダムな選択をすることでこれを避けていく。

Soft-max action selection

ε-Greedyの悪い点はランダムに探索するときに残りのアームをすべて同じ確率でランダムに選択してしまうところ。直感的には、良さそうなアームに割合を多めに振った方がこれまでの履歴から貪欲に選択したアームよりは良いアームがある可能性が高い。 temperatureパラメータを導入して、 temperatureが高いほど「試す価値がある」状態となる。つまり temperature＝０だと貪欲法と同じ。

Non-stationary Problem(非定常なケース)

スタンフォードビジネススクールの資料、てかこんなのやるんですね。

Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards | Stanford Graduate School of Business

アームの行動戦略

Gradient-Bandit

確率勾配法をバンディットに当てはめたケース。あまり踏み込まなくても良さそう。

Flaxman, Abraham D., Adam Tauman Kalai, and H. Brendan McMahan. "Online convex optimization in the bandit setting: gradient descent without a gradient." Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2005.