背景

看Sutton的Reinforcement learning: An introduction，里面將策略迭代作為一種基于動態規劃的方法。

書中舉了個grid world的例子，非常符合書中的數學原理，有狀態轉移概率，每個時間步就是每個state等.....

動態規劃作為一個常見的面試八股，經常出現于筆試題中，一般都是利用價值-動作表來去解決。

網上查了查，貌似目前全網所有的策略迭代的例子都是grid world這個例子，雖然很清晰，但是受限于這個問題框架，不舒服。

那么有意思的問題來了：如何使用策略迭代（Policy Iteration）解決01背包（knapsack 01）問題？

一、策略迭代

1、策略評估

給定策略\(\pi\)，計算其價值函數，即為策略評估，有時也稱其為預測問題。

根據貝爾曼方程：\(v_{\pi}(s) = \sum_{a}{\pi(a \mid s) \sum_{s', r}{P(s',r \mid s,a)(r + \gamma v_{\pi}(s'))}}\) 不斷迭代，直至收斂，具體的偽代碼算法如下：

2、策略改進

求解最優的策略和價值函數，即為策略改進，有時也稱其為控制問題。

策略改進定理：如果對于任意 \(s \in S\)，\(q_{\pi}(s, \pi'(s)) \geq v_{\pi}(s)\)，那么策略 \(\pi'\) 不會比策略 \(\pi\) 差（一樣好或者更好）。

構造一個貪心策略來滿足策略改進定理：
\( q_{\pi}(s, a) = \sum_{s', r} P(s', r \mid s, a) \left[ r + \gamma v_{\pi}(s') \right] \)
\( \pi'(s) = \arg\max_{a} q_{\pi}(s, a) \)
可知通過執行這種貪心算法，我們就可以得到一個更好的策略。

3、策略迭代算法流程

二、策略迭代代碼解決01背包問題

根據我調試的經驗，解決01背包問題要比解決完全背包問題更加麻煩一點。

問題在于：01背包問題中每一個物品只能拿取一次，而完全背包可以多次重復拿取。
GitHub倉庫中是代碼，因為順手打開的matlab就用matlab實現了，改一下語法就是python。

https://github.com/Tylerr77/Policy-Iteration-Solving-01-Knapsack-Problem?tab=GPL-3.0-1-ov-file

% 0/1 背包問題的策略迭代
clc;
clear;
%% 輸入
w = [2, 3, 4, 5, 6, 7, 8]; % 物品的重量
r = [3, 1, 5, 6, 7, 8, 9]; % 物品的價值，獎勵

max_W = 9; % 背包容量

n = length(w); % 物品數量

P = 1; % 因為選取下一個物品是固定的，所以狀態轉換的概率是1

gama = 1; % 衰減因子

% 初始化策略
policies = randi([0, n],1, max_W + 1) % 策略數組，數值表示某狀態時放入物品的index，0表示不選擇

% 初始化價值函數
% 代表V(s)，也就是V的index代表了每個狀態下所能得到的最大價值，
% V(s)表示 背包容量為s - 1 狀態時的價值函數（matlab索引從1開始）
V = zeros(1, max_W + 1)  % 背包容量從 0 到 W，每個容量的最大價值初始化為 0

% 策略迭代過程
while true
    % 步驟 1：策略評估
    % 使用當前策略計算每個狀態的價值函數
    disp('策略評估');
    V_new = V; % 用于存儲更新后的價值函數

    % 根據貝爾曼方程計算所有狀態s的狀態值函數
    % 迭代的方式進行策略評估，直到價值函數收斂
    while true
        f = 0;
        for s = 2:(max_W + 1)
            % ------------不同環境這段代碼不同-------------- %
            % 評估當前策略下，s狀態下的V(s)
            if policies(s) ~= 0 && w(policies(s)) <= s - 1
                V_new(s) = P * (r(policies(s)) + gama * V(s - w(policies(s))));
            else
                V_new(s) = V_new(s - 1);
            end
            % --------------------------------------------- %

            f = max(f, abs(V_new(s) - V(s)));
        end

        if f < 1e-6
            break;
        else
            V = V_new;
        end

    end

    % 步驟 2：策略改進
    % 根據當前值函數 V，選擇每個狀態下的最優動作
    disp('策略改進');
    policy_new = policies;
    
    policy_new(1) = 0; % s = 1背包沒有空間，策略一定是不選擇

    value_q = zeros(max_W + 1, n + 1); % q(s, a) 狀態-動作對價值函數
    for s = 2:(max_W + 1)
        for a = 2:n + 1 % a = 1代表什么都不放，= 2放1號物品，= 3放2號物品....
            
            % ------------不同環境這段代碼不同-------------- %
            % 01背包，物品僅僅可以被選中一次，但是什么都不放可以多次選中
            % 計算動作價值函數
            store = s; flag = 0;
            while store - w(a - 1) >= 1
                if policy_new(store - w(a - 1)) == a - 1
                    flag = 1;
                    break;
                end
                store = store - w(a - 1);
            end

            if flag ~= 1 && w(a - 1) <= s - 1
                value_q(s, a) = r(a - 1) + V(s - w(a - 1));
            else % 什么都不放，或者放不進去，則繼承上一個狀態的價值，價值為value_q(s - 1)
                value_q(s, a) = value_q(s, a - 1);
            end

            % --------------------------------------------- %

        end
        [max_q, max_act] = max(value_q(s,:));
        policy_new(s) = max_act - 1;
    end

    % 如果策略沒有變化，表示已經收斂
    if all(policy_new == policies)
        disp('策略已收斂');
        break;
    else
        % 更新策略
        policies = policy_new;
    end

end


% 輸出最終策略和最大價值
disp('最優策略:');
disp(policies); % 輸出最優策略 pi(s, a)
disp('最大價值:');
disp(V(max_W + 1)); % 輸出最大價值，背包容量為 W 時的最大值
weight = max_W + 1;
while weight ~= 0 && policies(weight) ~= 0
    fprintf('物品 %d: 重量 = %d, 價值 = %d\n', ...
        policies(weight), w(policies(weight)), r(policies(weight)));
    weight = weight - w(policies(weight));
end