強化学習のいくつかの文献で、suboptimality gapという言葉が出てくる。Google検索しても、それ自体にフォーカスした記事が出てこないため、そもそもなぜこの概念が重要なのかがわからない。
TLDR: 最適な腕の平均報酬からの各腕の報酬の差$\Delta_i$を考えたり、最適な腕の平均報酬からの２番目にベストな腕の報酬の差$\Delta$を考えることでRegretを捉えるのに役立つ。表記の揺れは文献により異なるが、多様なBanditの設定で、$\Delta$が既知の場合（比較的簡単な問題設定）や未知の場合（ややこしい場合）などで、研究者たちはさまざまな手法を用いてregretを$\Delta$以外で不等式で漸近的にとらえようと頑張っていることがわかった。
最適な腕の平均報酬からの各腕の報酬の差
Multi-armed banditの文脈では、ある腕$i$における報酬の平均を$\mu_i$としたとき、さまざまな腕に関して$\mu_i$が最大であるもの、すなわち平均報酬が最大となるような腕の報酬を$\mu_*$とする。
このような設定下である腕$i$のsuboptimality parameterは以下となる。
\Delta_i=\mu_*-\mu_i
このsuboptimality parameter$\Delta_i$を儲けることによって何がいいのかというと、psudo-regretが簡潔にかけるということだ。上記のサーベイ論文のSection 2では色々変形をすると以下に要約される:
\overline{R}_n=...=\sum_{n=1}^K\Delta_i\mathbb{E}T_i(n)
Multi-armed banditの文献のいくつかでは、いつもregretがどうなるかを捉えようとすることが多い。Regret boundsやRegret analysisというセクションのついた論文が多い。
例えば、Multi-armed banditの文献でよく見る以下の不等式（上記のサーベイ論文のTheorem 2.2）も、$\Delta_i$で表せる。また、$\Delta$をCtrl+Fで論文内で検索しても、さまざまなBandit問題の設定で多数ヒットするため、重要な概念であることは間違いない。
\liminf_{n \to +\infty} \frac{R_n}{\ln n} \geq \sum_{i: \Delta_i > 0} \frac{\Delta_i}{\mathrm{kl}(\mu_i, \mu^*)}
最適な腕の平均報酬からの２番目にベストな腕の報酬の差
(Minimal) sub-optimality gapといって、最適な$\mu_*$の次に最適な腕の報酬を$\mu
'$とした時、次のように最適な腕の平均報酬から、２番目に最適な腕の平均報酬との差を考えることがある。これは前のセクションの$\Delta_i$の２番目に最適な腕を$i$に当てはめた時の値だ。
\Delta=\mu_*-\mu'
所感
表記や言葉のゆれはさておき、regretの数式を捉える上で、最適な腕の報酬から別の腕の差を考えることで、regretの数式が表現できることがわかった。Multi-armed banditではregretの最小化をすることにより報酬の最大化をするので、regretを理論的に考える上で$\Delta_i$, $\Delta$は便利だ。
もちろん、実際のところ、そもそも最適な腕$\mu_*$がわかっていたら、regretの最小化、すなわち、報酬の最大化をする必要はない。実際のところ、結局何がしたいのか？
上記のsub-optimality gap$\Delta$が既知の場合（次の論文のセクション4）と、既知でない場合の議論（次の論文のセクション5）がよく見られる。この広い宇宙の中で、既知である問題設定は多くないような気がする。それもあって、次の論文では、$\Delta$が未知の場合でもregretを捉えられるような理論的な工夫をしている。
まとめ
最適な腕の平均報酬からの各腕の報酬の差$\Delta_i$を考えたり、最適な腕の平均報酬からの２番目にベストな腕の報酬の差$\Delta$を考えることでRegretを捉えるのに役立つ。表記の揺れは文献により異なるが、多様なBanditの設定で、$\Delta$が既知の場合（比較的簡単な問題設定）や未知の場合（ややこしい場合）などで、研究者たちはさまざまな手法を用いてregretを$\Delta$以外で不等式で漸近的にとらえようと頑張っていることがわかった。