强化学习入门之多臂赌博机问题

发表于 | 更新于 | 机器人学

基本概念

强化学习就是智能体（agent）在与环境（environment）的交互过程中为了达成一个目标（goal）而进行的学习过程。

reward是即时的，goal是长远的。

K臂赌博机问题

现在假设，你要重复地在 $k$ 个选项或动作中进行选择，每种选择的收益都符合各自的一个平稳的概率分布，你的目标是在某一段时间内最大化期望总收益的期望。
即：在一个老虎机（赌博机）上有多个操作臂，每次操作一个操作臂之后玩家可以获得一个奖励，玩家需要找到获利最大的操作方式。

现在假设老虎机的每个操作臂对应的收益都满足一个均值和方差恒定的高斯分布，那么我们可以通过大量采样的方式来推测出各操作臂对应收益的均值。

原理论述：
将在时刻 $t$ 选择的动作记作 $A_t$ ，并将对应的收益记作 $R_t$ ，任一动作 $a$ 对应的价值，是给定动作 $a$ 时获得收益的期望，记作 $q_{\ast}(a)$ ：

$$ \begin{gather} q_{\ast}(a) = \char"1D53C [R_t | A_t=a] \end{gather} $$

如果能知道每个动作的价值，那么每次选择价值最高的动作即可，然后更多的时候我们不能确切地知道动作的价值，不过我们可以估计。将动作 $a$ 在时刻 $t$ 的价值估计记作 $Q_t(a)$ 我们希望这个期望值接近 $q_{\ast}(a)$ 。

在任一时刻都至少会有一个动作的估计价值是最高的，称对应的动作为贪心动作。当你从这些动作中进行选择时，我们称“开发”当前你所知道的关于动作的价值的知识。

“动作-价值方法”

样本平均法，计算实际收益的平均值来估计动作的价值

$$ \begin{gather} Q_t(a) = \frac{t时刻前通过执行动作a得到的收益总和}{t 时刻前执行动作a的次数} = \frac{ \Sigma_{i=1}^{t-1} R_i 1 _{A_i=a}}{ \Sigma_{i=1}^{t-1} 1 _{A_i=a}} \end{gather} $$

在k臂赌博机中，a的取值为任意一个操作臂。
根据大数定律，只要我们对一个行动不断地尝试，这个估计的平均值就会无限地接近真实的期望值。

样本平均法公式：

$$ \begin{align} Q_{n+1}=\frac{1}{n} \sum_{i=1}^{n} R_i \end{align} $$

策略函数：

$$ \begin{gather} A_t = argmax_a Q_t(a) \end{gather} $$

即：取使$Q_t(a)$最大的动作 $a$ ，如果有多个行动价值都是最大，那么就随机选择一个。这是贪婪策略（Greedy）。简单的贪婪策略并不可取。
$\epsilon$ -Greedy : 在大多数情况下选取贪婪的策略，但是偶尔以一个很小的概率 $\epsilon$ 在所有的动作中做出随机的选择，这样可以保证每一个状态都能得到一定的探索。（类似于模拟退火、遗传算法中的变异等概念）

增量式计算

下面的公式中$Q_n$表示某动作被选择$n-1$次后的动作价值估计，$R_i$表示这一动作被选择$i$次时获得的收益

$$ \begin{gather} Q_n = \frac{R_1+R_2 + \cdots + R_{n-1}}{n-1} \end{gather} $$

在上面的程序中，我们每次执行完动作之后都要记录一次收益，存储过去的信息需要大量的内存空间和计算资源，我们可以将上述公式稍加变形来迭代更新收益的均值：

$$ \begin{align} Q_{n+1} & = \frac{1}{n} \sum_{i=1}^{n} R_i \notag \\ & = \frac{1}{n}(R_n + \sum_{i=1}^{n-1} R_i) \notag \\ & = \frac{1}{n} (R_n + (n-1) \frac{1}{n-1}\sum_{i=1}^{n-1} R_i) \notag \\ &= \frac{1}{n} (R_n + (n-1) Q_n) \notag \\ &= \frac{1}{n} (R_n + n Q_n - Q_n) \notag \\ &= Q_n + \frac{1}{n} (R_n- Q_n) \\ 新的估计值 & \gets 旧的估计值 + 步长 \times (目标 - 旧估计值) \\ New Estimate &= Old Estimate + LearningRate \times error(Reward Prediction Error) \notag \end{align} $$

上式在$n=1$时也成立。

奖励随时间可能变化（非平稳问题）

上面（6）式中的 $\frac{1}{n}$ 意味着随时间的增长，越靠后的学习率越低，如果我们面临的问题的奖励可能随时间变化的，那么应该考虑使用恒定的学习率，例如将 $\frac{1}{n}$ 替换为 $\alpha$ ：

$$ \begin{align} Q_{n+1}&=Q_n + \alpha (R_n- Q_n) \notag \\ &=(1- \alpha)^n Q_1 + \sum_{i=1}^{n} \alpha (1- \alpha)^{n-i} R_i \end{align} $$

这是一个加权平均，时间越早，权重越小。

matlab实现10臂赌博机测试平台

假设有一个10臂平台，matlab实现如下

matlab

% k-armed bandit ,k臂赌博机问题
% 参数说明
% k : 多臂赌博机的臂数，应该是大于等于2的正整数
% true_values : 预设的真实奖励
% start_v : 乐观初始值
% epsion_v : 贪心策略
% num_steps : 训练步数

clear
k=10;
true_values = 1:k; % 初始化真实臂的价值（1、2、3、4、5）
% true_values = [0.81,1.8,1.2,2.0,0.5,1.5,0.91,0.6,0.15,0.7];
start_v = 500; %初始值，一个较大的初始值
epsion_v = 0.1; %贪心策略
num_steps = 1000; %训练步数

% 初始化
estimated_values = ones(1,k)*start_v; % 初始化估计的臂的价值，记录了对不同臂的预期奖励
% 初始化统计每个臂的选择次数和累积奖励
action_counts = zeros(1, k);
total_rewards = zeros(1, num_steps);
% 初始化记录最优动作选择次数的数组
optimal_action_counts = zeros(1, num_steps);
optimal_action= max(true_values);

% epsilon-greedy算法
for step = 1:num_steps
    if rand() < epsion_v
        % 以ε的概率随机选择一个动作
        action = randi(k);
    else
        % 以1-ε的概率选择当前估计为最佳的动作
        [~, action] = max(estimated_values);
    end
    % 模拟选择动作后获得的奖励，奖励服从以真实价值为均值、方差为1的高斯分布
    reward = normrnd(true_values(action), 1);

    % 更新估计的臂的价值
    action_counts(action) = action_counts(action) + 1;
    estimated_values(action) = estimated_values(action) + (reward - estimated_values(action)) / action_counts(action);

    % 记录累积奖励
    if step == 1
        total_rewards(step) = reward;
    else
        total_rewards(step) = total_rewards(step-1) + reward;
    end
    % 记录选择的最优动作
    if action == optimal_action
        optimal_action_counts(step) = 1;
    end
end

% 计算平均收益
average_rewards = total_rewards ./ (1:num_steps);
% 计算最优动作占比
optimal_action_percentage = cumsum(optimal_action_counts) ./ (1:num_steps);

% 绘制平均收益随训练步数变化的曲线图
figure(1)
subplot(2,1,1);
plot(1:num_steps, average_rewards);
title("K臂赌博机实验")
% xlabel("训练步数")
ylabel("平均收益")
grid on;
hold on;
subplot(2,1,2);
plot(1:num_steps, optimal_action_percentage);
% title('最优动作占比随训练步数变化的曲线图');
xlabel('训练步数');
ylabel('最优动作占比');
grid on;
hold on;

结果类似下图：

k臂赌博机计算结果k臂赌博机计算结果