强化学习作业 3

Problem 1

对应于从 S 出发的单源最短路问题。容易得到一种最优策略

最优策略不唯一。

Problem 2

构建矩阵

n = 4;
m = 4;
id[i_, j_] := m (i - 1) + j;
row[idx_] := Quotient[idx - 1, m] + 1;
col[idx_] := Mod[idx - 1, m] + 1;

pfunc[a_, s_, t_] := Switch[a,
   1, If[row[s, m] == 1, If[t == s, 1, 0], 
    If[t == id[row[s] - 1, col[s]], 1, 0]],
   2, If[row[s, m] == n, If[t == s, 1, 0], 
    If[t == id[row[s] + 1, col[s]], 1, 0]],
   3, If[col[s, m] == 1, If[t == s, 1, 0], 
    If[t == id[row[s], col[s] - 1], 1, 0]],
   4, If[col[s, m] == m, If[t == s, 1, 0], 
    If[t == id[row[s], col[s] + 1], 1, 0]]
   ];
rfunc [a_, s_] := If[pfunc[a, s, 1] == 1, 0, -1];
r = Table[rfunc[a, s], {a, 4}, {s, n m}];
p = Table[pfunc[a, s, t], {a, 4}, {s, n m}, {t, n m}];

价值迭代算法

valueIteration[r_, p_, v0_, \[Epsilon]_, \[Gamma]_] := 
  Module[{k, v, vlast},
   k = 0;
   v = v0;
   While[k == 0 || Norm[v - vlast] > \[Epsilon],
    vlast = v;
    v = Table[
      Max[Table[
        r[[a, s]] + \[Gamma] p[[a, s]] . vlast, {a, Length[r]}]], {s, 
       Length[v0]}];
    Print[k, v];
    k = k + 1;
    ];
   Print["Converged in ", k, " iterations"];
   Return[v];
   ];

运行算法，得到输出

1	v = valueIteration[r, p, ConstantArray[0, n m] , 0.1, 1]

贪心选择策略

greedyPolicy[r_, p_, v_, \[Gamma]_] := 
  Table[Ordering[
     Table[r[[a, s]] + \[Gamma] p[[a, s]] . v, {a, 
       Length[r]}], -1][[1]], {s, Length[v]}];
printPolicyTable[\[Pi]star_] := 
  ArrayReshape[{"\[UpArrow]", "\[DownArrow]", "\[LeftArrow]", 
      "\[RightArrow]"}[[\[Pi]star]], {n, m}] // MatrixForm;

运行了 6 轮

第三轮得到的价值表为 {0,0,-1,-2,0,-1,-2,-3,-1,-2,-3,-3,-2,-3,-3,-3}, 对应的策略为

最后得到的价值表为 {0,0,-1,-2,0,-1,-2,-3,-1,-2,-3,-4,-2,-3,-4,-5}

最后的最佳策略为

与第一问得到的结果几乎是一致的。

Problem 3

policyIteration[r_, p_, \[Pi]0_, \[Epsilon]_, \[Gamma]_, n_] := 
  Module[{k, v, \[Pi], \[Pi]last},
   k = 0;
   \[Pi] = \[Pi]0;
   v = ConstantArray[0, Length[\[Pi]0]];
   While[k == 0 || Norm[\[Pi] - \[Pi]last] > \[Epsilon],
    Do[v = 
      Table[r[[\[Pi][[s]], s]] + \[Gamma] p[[\[Pi][[s]], s]] . v, {s, 
        Length[\[Pi]0]}], n];
    \[Pi]last = \[Pi];
    \[Pi] = 
     Table[Ordering[
        Table[r[[a, s]] + \[Gamma] p[[a, s]] . v, {a, 
          Length[r]}], -1][[1]], {s, Length[v]}];
    Print["k = ", k];
    Print["v = ", v];
    Print["\[Pi] = ", \[Pi]];
    k = k + 1;
    ];
   Print["Converged in ", k, " iterations"];
   Return[\[Pi]];
   ];