用Octave计算马尔可夫决策过程问题
 
广告
{{v.name}}
马尔可夫决策过程的核心要素：
状态（State）
动作（Action）
奖励（Reward）
转移概率（Transition Probability）
折扣因子（0~1），越近的奖励越重要
马尔可夫决策过程的核心公式：
1. 状态价值函数 V (s)
在状态 \(s\)，按策略 π 一直走下去，未来总奖励期望：
\(V(s) = \mathbb{E} \left[ \sum_{t=0}^{\infty} \gamma^t R_{t+1} \mid S_0 = s \right]\)
2. Bellman 方程
\(V(s) = \max_a \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V(s') \right]\)
马尔可夫决策过程的标准解法：
方法1：价值迭代（最简单、最常用）
不断迭代更新 V (s)，直到收敛。
步骤：
1. 初始化所有 \(V_0(s)=0\)
2. 对每个状态 s，用 Bellman 公式更新：
\(V_{k+1}(s) = \max_a \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V_k(s') \right]\)
3. 重复直到 \(V\) 变化很小
4. 最后从 V 反推最优策略：
\(\pi^*(s) = \arg\max_a \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V(s') \right]\)
方法2：策略迭代
1. 随便给一个初始策略
2. 策略评估：算当前策略的 V(s)
3. 策略改进：用 V(s) 贪心更新策略
4. 重复到策略不变
方法3：Q 迭代（Q-learning 前身）
直接更新动作价值 Q(s,a)：
\(Q(s,a) = (1-\alpha)Q(s,a) + \alpha[R(s,a) + \gamma \max_{a'} Q(s',a')]\)
例子：
- 2 个状态：\(s_1, s_2\)
- 2 个动作：\(a_1, a_2\)
- 折扣因子 γ=0.9
- 在 \(s_1\) 选 \(a_1\)：一定到 \(s_2\)，奖励 +5
- 在 \(s_1\) 选 \(a_2\)：一定到 \(s_1\)，奖励 +1
- 在 \(s_2\) 选任意动作：一定停在 \(s_2\)，奖励 0
求解，代码如下：
>> % ========== MDP 价值迭代 ==========
% 状态数 S=2，动作数 A=2
S = 2;
A = 2;
gamma = 0.9;
tol = 1e-6;

% 转移概率 P(s_next, s, a)
P = zeros(S, S, A);
P(2,1,1) = 1.0;   % s1,a1 → s2
P(1,1,2) = 1.0;   % s1,a2 → s1
P(2,2,1) = 1.0;   % s2,a1 → s2
P(2,2,2) = 1.0;   % s2,a2 → s2

% 奖励 R(s, a)
R = zeros(S, A);
R(1,1) = 5;
R(1,2) = 1;
R(2,:) = 0;

% 价值迭代
V = zeros(S, 1);
while true
    V_new = zeros(S, 1);
    for s = 1:S
        q = zeros(A, 1);
        for a = 1:A
            q(a) = R(s,a) + gamma * P(:,s,a)' * V;
        end
        V_new(s) = max(q);
    end
    if max(abs(V_new - V)) < tol
        break;
    end
    V = V_new;
end

% 最优策略
pi = zeros(S, 1);
for s = 1:S
    q = zeros(A,1);
    for a =1:A
        q(a)=R(s,a)+gamma*P(:,s,a)'*V;
    end
    [~, pi(s)] = max(q);
end

disp('最优价值 V:'); disp(V);
disp('最优策略 pi:'); disp(pi);
----------
最优价值 V:
  10.0000
        0
最优策略 pi:
   2
   1
友链