リグレット解析のメモ

機械学習

MLP オンライン機械学習本でリグレット解析について勉強した際のメモ．

リグレット解析の概要

リグレット解析(regret analysis)はアルゴリズムが最適な戦略をとった場合と比べてどの程度悪かったのか， そのリグレット（後悔）を測ることでアルゴリズムの性能を測る． リグレット解析自体はオンライン学習だけでなく、ゲーム理論など広い問題設定で利用されている。

リグレット解析の定義

リグレット解析は次のような問題設定を扱う。 プレイヤーは毎回、可能なアクション集合{K}から1つのアクション{\theta \in K}を選択する。 その後に、コスト関数{f}が提示され、その回のコスト{f(\theta)}が決まる。 この操作を何回も繰り返していく。{t}回目のアクションを{\theta^{(t)}}、コスト関数を{f^{(t)}}とする。 コスト関数{f^{(t)}}は毎回全く違っていても、同じでも構わない。

プレイヤーのアクションを決める方法を戦略と呼ぶことにする。 プレイヤーはどのような戦略をとれば合計コスト{\sum^{(t)} f^{(t)}(\theta^{(t)})}を最小化できるか。 そもそもコスト関数{f^{(t)}}がわからない場合でも、合計コストを最小化できるような戦略をとることができるのか。

同じアクションしか取らない戦略を固定戦略と呼び、このアクションを{\theta^{\ast}}とする。 このとき、ある戦略{A}のリグレットは次のように定義される。

ある戦略Aに基づくアクションの合計コストと最適な固定戦略{\theta^{\ast}}による合計コストとの差を戦略{A}のリグレット {Regret_{T}(A)}という。 {} $$ Regret_{T}(A) = \sum_{i} f^{(t)}(\theta^{(t)}) - \sum_{i}f^{(t)}(\theta^{\ast}) $$ 最適な固定戦略をとっている場合と比べて、現在の戦略がどれだけ悪いのかを測り、「あの固定戦略をとっていれば」と考えるのでリグレットと呼ばれる。

戦略

Follow The Leader(FTL)

最も単純な戦略として、これまでのコストの合計を最小にするようなアクションを次のアクションとしてとる方法を考えてみる。 この戦略では{t}回目のアクション{\theta{(t)}}を次のように決定する。 {} $$ \theta^{(t)} = \arg \min \sum_{i=1} f^{(t)}(\theta) $$ この戦略はFollow The Leader(FTL)と呼ばれる。 一見うまくいくように見えるが、評価するコスト関数{f^{(t)}}はこれまでのコスト関数とは関係ないかもしれない場合には対応できない。

Regularized Follow The Leader(RFTL)

コスト関数以外にアクションを安定させることを考える。 {t}回目のアクション{\theta^{(t)}}を次のように決めることを考えてみる。 {} $$ \theta^{(t)} = \arg \min \sum_{i=1} f^{(t)}(\theta) + R(\theta) $$ ただし、{R(\theta)}は凸関数であり、{\eta \geq 0}はどの程度正則化を考慮するかのパラメータ。 この戦略をRegularized Follow The Leader(RFTL)と呼ぶ。

（諸々の証明はとばす）

コスト関数の正則化関数で割ったノルム{\lambda}を、 {} $$ \lambda = \max \, f^{(t)T} (\nabla^{2}R(\theta))^{-1} f^{(t)} $$ とし、
実行可能領域の正則化関数で割った直径{D}を、 {} $$ D = \max R(\theta)-R(\theta^{(1)}) $$ とすると、
RFTLのリグレットは次のようになる。 {} $$ Regret_{T}(A) = \sum_{i} f^{(t) T}(\theta^{(t)} - u) \leq 2 \sqrt{2 \lambda D T} $$

この式のリグレットには{\lambda}と{D}が含まれている。 この2つの値はトレードオフの関係にある。 もし{D}を小さくしたいのであれば、({D=\max R(\theta)-R(\theta^{(1)})}なので）、{R(\theta)}と{R(\theta^{(1)})}が小さくなるような{R}を使いたくなる。 しかしその場合、{\nabla^{2} R(\theta)}の各要素は小さく、その逆行列は大きくなるため、{\lambda}は大きくなる。 問題の特徴を活かして、{D}と{\lambda}の両方が小さくなるような正則化関数、コスト関数を設計する必要がある。