https://papers.nips.cc/paper/6188-bayesian-optimization-with-a-finite-budget-an-approximate-dynamic-programming-approach.pdf

N回しか関数実行ができないという設定のもとでのBayesian Optimizationのアルゴリズムを考える論文。 Bayesian Optimizationは基本的に次のステップだけを考えるgreedyなアルゴリズムであるが、この論文ではrollout[1]という近似DPアルゴリズムを活用して数ステップ分の先を考慮しながら選択を行う手法を提案している。

はじめに、N-step目までの報酬をなるべく大きくするためには1-step目の選択をどうするべきかを考える。
k-step目のrandom disturbanseをwr、control(方策と考えて良い)をur、状態をzr、得られる報酬をrk(zk, uk, wk)、動的システムの状態を吐き出す関数をF(zk, uk, wk)とすると、N-step目に得られる報酬をなるべく大きくするためには、以下の式を入れ子式に解いていき、最後に得られたu1=J1(z1)を1-step目の方策として採用すれば良いわけである： f:id:toaruharunohi:20170619221527p:plain （なお上記の期待値はrandom disturbanseについてとっている）

Bayesian OptimizationのN回目までの利得関数の和を最大化したい場合には、上記の報酬r_kとして対象とする利得回数をそのまま採用すれば良い。が、上記の式をそのまま解くのは大変である。

そこで、入れ子式に最大値を求めていくことにより最適な方策を求めるという戦略を捨て、代わりに最適なpolicyと近そうなbase policy πをこちら側で定義して(後方の説明参照)、そのpolicyを用いて次のステップのxを選択するという戦略を採用する。こうすることで非常に計算の大変な入れ子式に最大値を求める処理を省略することが可能になる。
また、期待値を計算する際は実際に積分を計算することは困難なのでガウス-エルミート求積法による近似計算に置き換える。
まとめると以下の式中に出てくるH~n(Sn)で上記のJnを置き換えることになる： f:id:toaruharunohi:20170619223328p:plain なおαnはガウス-エルミート求積法の係数である。またSnはサンプリングしたxとそのxをもとにGPからサンプリングした出力値fのペアの集合である：