Exploration-Exploitation

MCMC 法を用いた最適化法ではお互いに両立しがたい二つの要請がある． 一つは，最適化問題を効率的に解くために，できるだけ広い空間をむらなく 探索したいということである． そのためには提案分布はできるだけ $\cal X$ 上を広く飛び回るものである必要がある(Exploration)．

一方で，MCMC 法では採択と棄却というステップが入るため，候補が採択されなければ 意味がない． 採択されやすい候補というのは単純に言えば現時点の $x_t$ よりも確率値ができるだけ高いもの(つまり $f(x_t)$ の値が小さいもの)である． これは $f(x)$ に何も仮定を入れなければどうしようもないが，たとえば $f(x)$ に弱い連続性のようなものを仮定すると，今まで $f(x)$ の値が 小さかったところの周りはやはり値が小さいと思われるので，その周りに 集中して候補を出すようにすれば，高い確率で採択されるかもしれない (Exploitation)． しかし，それでは最初のできるだけ飛び回って欲しいという要請には 矛盾してしまう．