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是 epsilon 的缩写，一个很小的数字，可能应该是一个额外的输入。）

对于每次迭代，您都希望对每个状态采取最佳行动。最好的行动是产生最大回报的行动，按概率加权。就是这样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 回答