🙌

Bandit Algorithm Tor Lattimore Solution to Exercise 20.5

3 min read

Deep Mindの理論研究家であるTor Lattimoreが最近出した本Bandit Algorithmを輪読しています.ここではその練習問題の解答を上げていこうと思います.間違っているかもしれないので参考程度にお願いします.ミスがあったら,教えてくれると助かります.

今回はExercise 20.5.です.

本文中のLemma 20.3を証明せよという問いですが,ただの確率過程の問題と捉えて解けます.

Lemma 20.3は以下のような命題です.

h\mathrm{R}^d上の確率測度とする.\bar{M}_t = \int_{\mathrm{R}^d}M_t(x)dh(x)\mathrm{F}-adaptedで非負なスーパーマルチンゲールであり,\bar{M}_0 = 1であることを証明せよ.

ここで,M_t(x) = \exp(\langle x, S_t \rangle - \frac12 \|x\|_{V_t}^2)です.今回はS_tが具体的になんなのかということは必要なくM_t(x)F-adaptedで,非負なスーパーマルチンゲールであることだけ使います.

証明

\bar{M}_t(x)が非負であることは,M_t(x)が非負であることから従います.

次に\bar{M}_t\mathcal{F}_t-可測であることを示します.これはKallenbergのFoundation of Modern ProbabilityのLemma 1.26を使います.主張は,

二つの可測空間(S, \mathcal{S})(T, \mathcal{T})があり,可測関数f: S \times T \rightarrow \mathrm{R}_+S上の\sigma-有限な測度\muが存在するとします.このときf(s,t)は任意のt \in Tにおいて\mathcal{S}-可測であり,関数\mu f(\cdot, t)\mathcal{T}-可測である.

fM_tと思い,\mu f\int M_t(x) h(x) = \bar{M}_tと思えば,\bar{M}_t(x)\mathcal{F}_t-可測であることがわかります.

最後にスーパーマルチンゲールであることを証明します.つまり,確率1で

\mathrm{E}\big[\bar{M}_t|\mathcal{F}_{t-1}\big] \leq \bar{M}_{t-1}

を示したいです.

背理法を使います.

\Pr(\mathrm{E}\big[\bar{M}_t|\mathcal{F}_{t-1}\big] - \bar{M}_{t-1} > 0) > 0

を仮定します.

すると,ある正の整数\varepsilon > 0が存在して,

A = \{\omega : \mathrm{E}[\bar{M}_t|\mathcal{F}_{t-1}](\omega) - \bar{M}_{t-1}](\omega) > \varepsilon\} \in \mathcal{F}_{t-1}

で,\Pr(A) > 0となる事象Aが存在する.

すると,A \in \mathcal{F}_{t-1}と条件付き期待値の定義から

0 < \int_A (\mathrm{E}[\bar{M}_t | \mathcal{F}_{t-1}] - \bar{M}_{t-1})d\mathrm{P} = \int_A (\bar{M}_t - \bar{M}_{t-1})d\mathrm{P}

次に\bar{M}_tの定義から,

\int_A (\bar{M}_t - \bar{M}_{t-1})d\mathrm{P} = \int_A \int_{\mathrm{R}^d}(M_t(x) - M_{t-1}(x))dh(x)d\mathrm{P}

Fubini-Tonelliの定理より,積分順序を交換しても良く,

\int_{\mathrm{R}^d}\int_A (M_t(x) - M_{t-1}(x))dh(x)d\mathrm{P} = \int_A \int_{\mathrm{R}^d}(M_t(x) - M_{t-1}(x)))d\mathrm{P}dh(x)

最後にM_tのスーパーマルチンゲール性を使えば,

\int_A \int_{\mathrm{R}^d}(M_t(x) - M_{t-1}(x)))d\mathrm{P}dh(x) \leq 0

よって,0 < 0となり矛盾.

Discussion

ログインするとコメントできます