強化学習、とりわけMulti-armed bandit（多腕バンディット問題）の設定で、regretを最小にしようとする状況がよくあります。regretのtステップごとの変化を実験的に観察する議論も見られます。それは、例えばMulti-armed bandit (以下、MABと呼ぶ。)の文脈などです。この記事はregretのいくつかの形(instantenous regret $r_t$, cumulative regret $R_t$, average regret $R_t/T$)に触れ、そこからグラフの形についてまとめます。
Regretのおさらい
大ヒットをして現時点で2841回も引用されている論文（ICMLの賞も受賞）[1] Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design を参考にします。
Regretとは: (最適な選択を知らなかったことによる、最適な場合の報酬)-(実際の選択による報酬) だと言えます。
$f$を未知の関数として、ステップ$t$における選択は$\boldsymbol{x}_t$、また、$f$を最大化するような選択を$\boldsymbol{x}^*$としたときの場合を考える。ある時点での瞬間のregret($r_t$)は以下となる。
r_t= f(\boldsymbol{x}^*)-f(\boldsymbol{x}_t)
この瞬間的なregret($r_t$)をステップ$t$について足し合わせたものがcumilative regret ($R_t$)である。
Cumulative regretのグラフでの直感
今読んでいる論文は開示できないのですが、Cumulative regretのグラフはいろいろなところで見ます。例えば、次のバンディットアルゴリズムのまとめの記事では、Cumulative regretの可視化がたくさんあります。
Cumulative regretのグラフから、アルゴリズムの挙動は直感的には以下のように解釈できるでしょう。
Average regretのグラフでの直感
とある文献、[1] Gaussian Process Optimization in the Bandit Setting:
No Regret and Experimental DesignのFig. 5に注目してみましょう。
Fig. 5の縦軸は "mean average regret"であると示されています[1]。これは"cumulative regret"とは違います。"average regret" とは$R_t/T$としてcumulative regretを総ステップ数で平均を取ったものです[1]。論文中[1]では、MABの設定でアルゴリズムが満たすべき望ましい漸近的な特徴として、この"average regret" とは$T\rightarrow0$の時に$R_t/T\rightarrow0$となることだと述べられています。(注：Fig. 5のMean average regretというのは、average regretを多数観察して、それをMeanをとったことのようです。Meanとaverageが同時に出てきてややこしいですね。通常の理論的な文脈では"average regret"と書かれています。)
今までの流れをまとめると次のような望ましいアルゴリズムと、望ましくないアルゴリズムのaverage regretに関する挙動が想像できるでしょう。
つまり、もし論文中で"average regret"のステップごとの推移をグラフで示している場合は、上記の望ましい特徴を各アルゴリズムが示しているかを可視化する目的があるのでしょう。
次にわかりたいこと
以下は、個人的な学習の目標です。
Regret boundsについて大まかに理解したい。
強化学習でrewardを最大化することは、裏を返せばregretを最小化することです。この文脈で、Regret boundsという言葉がさまざまな論文で出てきます。([1]に限られない。)しかし、それは何のregretについてなのか、また、それはupper boundsなのか、lower boundsなのか曖昧です。regret自体に関しても、これまでの議論からでもいくつか可能性が出てきます。
- $R_t$ cumulative regret
- $R_t/T$ average regret
- $r_t$ instantenioues regret （上述の瞬間的なregret）
大ヒットをして現時点で2841回も引用されている[1]の論文（ICMLの賞も受賞）でも、単に"4. Regret Bounds"とだけあります。それに後続する論文でも当たり前のようにregret boundsへの言及がたくさん出てきます。別の論文でもregret analysisとしてBig O, Big-θ notationでregretに関して分析があります。これらが何なのか、もしくは今の所詳しく知る必要があるのかも含めて読んでいきたいと思います。わかったら記事また書きます。
ここまで読んでくれてありがとうございました。間違いがありましたら、コメントでお知らせください。