本項は、「本多淳也・中村篤祥著 バンディット問題の理論とアルゴリズム」の第1章を開設した分である。第1章は、あまり数式がなかったために、言い換えとなっている部分もある。
多腕バンディット問題とは
とある選択肢を選択すると、報酬が得られるとする。複数の選択肢（腕）を有限回の回数選び、得られる報酬を最大化しようとする時、どのように選択肢を選べばよいだろうか？
ここで問題なのは、選択者は各腕の報酬がどのように決まるかがわからない、という問題である。たとえば、いかなる状況設定にも関わらず一定値の報酬が得られるならば、各腕を1回ずつ選択し、報酬を確認してから報酬を最大化する腕を選べばよい。しかし、各腕が確率的に（平均10、分散2.5の正規分布に従う、など）ふるまうときは、問題がややこしくなる。どれが報酬が最大の腕なのかがわからなくなるのである。
選択者の方策の評価方法
今、多腕バンディット問題において、腕が$n$本あるとし、全部で$T$回選択できるとする。時刻$t(=1,\cdots,T)$において、$i(=1,\cdots,n)$番目の腕の報酬を$X_i(t)$と表す。
すると全部で$T$回行ったときの報酬の総和、つまり累積報酬は
X_{i(1)}(1) + \cdots+ X_{i(T)}(T)
=
\sum_{t=1}^T X_{i(t)}(t)
となる。ただし$i(t)$は、$t$回目に選ばれる腕である。
ここで選択者の方策を評価したいとしよう。普通に考えれば各回における報酬の最大値
\max_i {X_{i}(1)} + \cdots+ \max_i {X_{i}(T)}
=
\sum_{t=1}^T \max_i {X_{i}}(t)
を考えれば、全試行における報酬を最大化できそうだが、これでは目標として高すぎる。そのため各回ではなく、報酬を最大化する腕を事前に1つだけ選ぶことで代替する。
\max_i \{X_{i}(1)+ \cdots+ {X_{i}(T)}\}
=
\max_i \sum_{t=1}^T{X_{i}}(t)
上記と累積報酬の差は、リグレット
\mathrm{Regret}(T)
=
\max_i \sum_{t=1}^T{X_{i}}(t) - \sum_{t=1}^T X_{i(t)}(t)
と呼ばれ、バンディット問題においてはこれを最小化することを考える。
期待リグレットと
E[\mathrm{Regret}(T)]
=
E\left[ \max_i \sum_{t=1}^T{X_{i}}(t) - \sum_{t=1}^T X_{i(t)}(t) \right]
擬リグレットと
\overline{ \mathrm{Regret} } (T)
=
\max_i E\left[ \sum_{t=1}^T{X_{i}}(t) - \sum_{t=1}^T X_{i(t)}(t) \right]
との間には、不等式
\overline{ \mathrm{Regret} } (T)
\leq
E[\mathrm{Regret}(T)]
が成り立つ。
忘備：この不等式は未証明。
用語
- 腕：選択肢、アーム(arm)とも。選択者が特定の腕を選ぶと、報酬がもらえる。私はできるだけ外国語を音のまま訳すのを良しとせず、語義をきちんと日本語に訳すのが良いと思っているので、これからは「腕」と表記する。
- 選択者：プレイヤーとも。腕を選び、報酬を受け取る主体。
- 探索：どの腕が報酬を多く出しやすいか、探ること。
- 知識活用：最も報酬を出しやすい腕を選択し、合計の報酬を増やそうとすること。
- 方策：ポリシーとも。選択者がどのように腕を選ぶかという戦略のこと。
- 確率的バンディット：各腕の報酬が何らかの確率分布に従って生成されること。
- 敵対的バンディット：選択者の方策を知っている敵対者が報酬を決めること。
書籍の紹介