1

マルコフ決定問題について学習しようとしており、値の反復のアルゴリズムが与えられましたが、それらを実際の C++ コードに変換する方法がわかりません。主に総和などが発生する部分。アルゴリズムは次のとおりです。

function VALUE-ITERATION(P;R) returns a utility matrix
    inputs: P, a transition-probability matrix
            R, a reward matrix
    local variables: U, utility matrix, initially identical to R
                     U', utility matrix, initially identical toR
    repeat
         U <- U'
         for each state i do
             U'(s_i) <-  R(s_i) + max_a Summation_j P^a_ij*U(s_j)
         end
    until max_(s_i) |U(s_i) - U'(s_i)| < e
return U

これは私には象形文字のように見えますが、もっと役立つ単純なアルゴリズムはありますか? それとも、誰かが私のためにそれを馬鹿にすることができますか?

4

2 に答える 2

3

私はこの記事をすぐに見つけました:マルコフ決定問題の値の反復とポリシーの反復アルゴリズム [PDF ファイル]。何が起こっているのかをかなり詳しく説明しています。

概念的には、いくつかの状態になるシステム、ある状態から別の状態への遷移に対する報酬、および場合によっては状態遷移をもたらす可能性のあるアクションがあります。基本的な考え方は、変更されないユーティリティ マトリックスに到達するまで繰り返し続けることです。それが、最終テストで求められるものmax_(s_i) | U(s_i) - U'(s_i)| < eです。(ここでeは、小さい数であるイプシロンの略で、おそらく追加の入力である必要があります。)

反復ごとに、各状態に最適なアクションを実行する必要があります。最善の行動とは、確率によって加重された、最大の報酬を生み出す行動です。それが何をするかmax_a Summation_j P^a_ij*U(s_j)です: 確率によって重み付けされた、最高の報酬を生み出す行動を見つけてください。

于 2012-12-04T20:33:50.967 に答える
2

少しずつ翻訳することはできますが、コードにはコンテキストでしか意味をなさない情報がたくさんあり、そのコンテキストを知る方法はありません。
また、P^a_ij はある時点で P の a_i 倍 j 乗したように見えるため、途中で一部の書式設定が失われたようです。デビッドは、クレイジーなビットを解釈する方法を知っているようです.
また、条件ループ|は奇妙な疑似コードで使用されますが、私は文字通りそれを取りました。

utility_matrix VALUE_ITERATION(const probability_matrix& P,
                               const reward_matrix& R)
{
    utility_matrix U(R);
    utility_matrix UP(R);
    do {
        U = UP;
        for(int s_i : ????) //for each state in what?
            UP[s_i] = R[s_i] + ???? //max_a Summation_j P^a_ij*U(s_j)
    while(max(s_i) ???? std::abs(U[s_i] - UP[s_i])<e);
    return U;
}

akira が言ったように、理解できるビットは簡単です。それができない場合は、これに取り組む前に C++ についてさらに学ぶ必要があるかもしれません。

あなたのコメントによると、あなたのアルゴリズムに漠然と似ている C コードを見つけました。(62～76行目)

于 2012-12-04T20:12:50.400 に答える