本項は、「本多淳也・中村篤祥著　バンディット問題の理論とアルゴリズム」の第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)とも。選択者が特定の腕を選ぶと、報酬がもらえる。私はできるだけ外国語を音のまま訳すのを良しとせず、語義をきちんと日本語に訳すのが良いと思っているので、これからは「腕」と表記する。
選択者：プレイヤーとも。腕を選び、報酬を受け取る主体。
探索：どの腕が報酬を多く出しやすいか、探ること。
知識活用：最も報酬を出しやすい腕を選択し、合計の報酬を増やそうとすること。
方策：ポリシーとも。選択者がどのように腕を選ぶかという戦略のこと。
確率的バンディット：各腕の報酬が何らかの確率分布に従って生成されること。
敵対的バンディット：選択者の方策を知っている敵対者が報酬を決めること。

書籍の紹介