ベイズの最適強化学習はどれくらい難しいですか?

$ n $ MDP(Markov decision processes)の集合を考えてみましょう。 MDP $ M
$はある確率分布$ xi $に従ってこの集合から選択され、次に$ T $の固定ポリシー$ pi $と対話して、$ V_
pi $の総期待報酬を得る(ここで期待値値はwrt $ xi $であり、$ M $でのランダム遷移、場合によっては$ pi
$によるランダムな決定です)。 $ V_ pi
$ができるだけ高いというようなポリシーを設計する問題は、強化学習として知られています(具体的には、モデルベースのベイズ補強学習の有限$
n $ modelsのセット)。 $ V_ pi $が可能な最高値$ V ^ * $と等しいポリシー$ pi
$はベイズ最適と言います。

Bayesの最適ポリシーの計算は扱いにくいと主張されているため、最適なBayesではなく、良いパフォーマンスの境界(PSRLやUCBアルゴリズムなど)を満たしているアルゴリズムを使用する必要があります。しかし、この難しさは複雑さの理論的な硬さの定理によってどれほど支えられているのか私は確信していませんか?

実際、この種の強化学習は、POMDP(部分的に観測可能なマルコフ決定プロセス)を解く特別なケースとみなすことができます。すなわち、初期状態でのランダムな遷移が観察できないように$
xi $をサンプリングし、その結果得られるMDP $ M $が以下の遷移を支配するPOMDP $ hat {M}
$を考えることができる。現在、PapadimitriouとTsitsiklisは1987年にを証明しました
.POMDPを解決することはPSPACE-hardです。証明は、QSATをPOMDPの値を計算することに減らすことによって機能します。さらに、削減を調べることで、それらが構築するPOMDPは、$
hat {M}
$!具体的には、最初に観測されたランダムな観測不能な遷移は、与えられたQSATインスタンスの式のを選択する役割を果たします。

したがって、PapadimitriouとTsitsiklisの結果は、Bayes最適方策を見つけることは困難であることを示しています(標準的な複雑さの理論上の仮定の下では)。しかし、特に、その証明はBayesの最適性が必要な場合にのみ有効です。これは、QSATインスタンスの普遍的な量指定子がMDPのランダム遷移に置き換えられているためです。これは、満たされない式でも高い報酬を得ることができる可能性があることを意味します。

現在では、金スミス、ルセナ、およびMundhenkは2001年に値を近似している近似するを証明しましたのPOMDPの難しいです。しかし、彼らの証拠では、POMDPは私たちが興味を持ったフォームのではありません。より正確には、$
hat {M} $という形式の
という基本的な構造から始めますが、基本的なPOMDPを何度も実行する確率増幅が必要です。状態の一部がランダムにリセットされます。

そう、AFAIK、それは可能性があるようです。上記のようにMDPと$ xi $のセットを受け取り、$ V ^ * $の$
ε$近似を生成する多項式時間近似スキーム。そのようなスキームは、ほぼベイズの最適方針($ V_ pi geq V ^ * –
T ε$)を計算するために使用することができます。そのような体系が存在するか?それともそれを禁じる別の定理がありますか?

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です