読者です 読者をやめる 読者になる 読者になる

主に、強化学習

情報系の大学2年生が確率に関連したことを多めに書いてるブログ

「Chernoff上界」について

はじめに

 Deep Learningの話題で沸騰中のなか、あまり騒がれない強化学習というものがありましてですね。
今それを勉強しているわけなんですが、その中で一番考え方の基礎となるのが「Multi-Armed Bandit問題」と呼ばれるものです。
北海道大学の資料?が日本語で解説されててとてもわかりやすいんではないかと思います。
ここで書いてることは勉強中で正確さは保証できないので悪しからず。 でですね、多腕バンディット問題について勉強してると、 cumulative \, regretと呼ばれる累積期待損失値が出てくるわけなんですが、各アクションに対してその期待損失値がどこまで保証されているのかという上界が知りたいわけです。上界は、上から抑えられている(bounded [from] above)と言われてます。
おっと、ここでキーワードになってくるのが、期待(損失)値上界なわけなんですが、上界を調べるためにChernoff上界というものをよく用います。つまるところ、確率に関連するキーワードということですね。
残念なことに日本の資料でChernoff上界について詳しく書かれてるものが確率と計算ぐらいではないんだろうか、ということで今回は多腕バンディット問題と織り交ぜながら話してみたいと思います。(久しぶりのブログにしては割りといい滑り出しじゃないかな?)

マルコフ不等式(Markov Inequality)

Chernoff上界 を理解する際にまず重要になってくるのが、マルコフ不等式というものです。このマルコフはマルコフ過程などは関係ないです。単なる確率で用いられる不等式です。高校数学の美しい物語さんのマルコフ不等式がとてもハラショーなので是非一度目を通してください。

高校数学の美しい物語、略して高美(こうび)で書かれてる「マルコフ不等式で言いたいのは、平均のk倍を越える確率が\frac{1}{k}以下である」と書かれてるのがとてもわかりやすいと思います。

非負な確率変数をXとし、0より大きい任意のaに対して、  Pr(X \ge a) \leq \frac{ E(X) }{a} がなりたつ.

これがマルコフ不等式ですね。

証明は簡単で

確率変数 Y = 1 \,  if \, X \ge a \, else \, 0とする。 X \ge 0なので、 Y \leq \frac{X}{a}です。  E(Y) =  Pr(X \ge a) \times 1 + Pr(X <  a) \times 0 = Pr(X \ge a)となります。

よって、  Pr(X \ge a) = E(Y) \leq E(\frac{X}{a}) = \frac{E(X)}{a} となります。

<続きあります…>

積率(moment)

Chernoff 上界(Upper Bound)

UCB1 algorithm