强化学习基础-多臂老虎机

强化学习关注智能体和环境交互过程中的学习，这是一种试错型学习（trial-and-error learning）范式。

问题定义

多臂老虎机问题被看作简化版的强化学习问题。与强化学习不同，多臂老虎机不存在状态信息，只有动作和奖励，算是最简单的“和环境交互中的学习”的一种形式。多臂老虎机中的探索与利用（exploration vs. exploitation）问题一直以来都是一个特别经典的问题。

在这个问题中，有一个有K根拉杆的老虎机（也称为臂），每个老虎机都有一个不同的固定概率分布R，表示玩家在拉动该老虎机臂时获得奖励r的概率。

玩家的目标是通过不断尝试不同的老虎机臂，操作T次拉杆后获得尽可能高的累积奖励。然而，玩家并不知道每个老虎机臂的概率分布，因此需要通过不断尝试和观察来逐步学习每个老虎机臂的概率分布，并根据学习到的信息做出最优的选择。由于奖励的概率分布是未知的，因此我们需要在“探索拉杆的获奖概率”和“根据经验选择获奖最多的拉杆”中进行权衡。

累积懊悔

多臂老虎机问题可以表示为一个元组<A,R>，其中：

• A为动作集合，其中一个动作表示拉动一个拉杆。若多臂老虎机一共有根拉杆，那动作空间就是集合$\left \{a_1,\ldots,a_k\right \}$，我们用 表示任意一个动作；
• R为奖励概率分布，拉动每一根拉杆的动作都对应一个奖励概率分布$\mathcal{R}\left(r \mid a\right)$，不同拉杆的奖励分布通常是不同的。

最大化累积时间的收益:$\max \sum_{t=1}^{T} r_{t}, r_{t} \sim \mathcal{R}(\cdot \mid a)$

累积懊悔

对于每一个动作a，定义其决策的期望收益:$Q\left(a^{i}\right)=\mathbb{E}_{r \sim \mathbb{P}\left(r \mid a^{i}\right)}\left[r \mid a^{i}\right]$

至少存在一根拉杆，它的期望奖励不小于拉动其他任意一根拉杆，其最优收益:$Q^{\star}=\max _{a^{i} \in \mathcal{A}} Q\left(a^{i}\right)$

懊悔(Regret)定义为拉动当前拉杆的动作与最优拉杆的期望奖励差，即决策与最优决策的收益差:$R\left(a^{i}\right)=Q^{\star}-Q\left(a^{i}\right)$

累积懊悔（cumulative regret / Total Regret）即操作 次拉杆后累积的懊悔总量:$\sigma_{R}=\mathbb{E}_{a \sim \pi}\left[\sum_{t=1}^{T} R\left(a_{t}^{i}\right)\right]$ MAB 问题的目标为最大化累积奖励，等价于最小化累积懊悔。$\min \sigma_{R}=\max \mathbb{E}_{a \sim \pi}\left[\sum_{t=1}^{T} Q\left(a_{t}^{i}\right)\right]$

估计期望奖励

算法：多臂老虎机 初始化:$Q\left(a^{i}\right):=c^{i}, N\left(a^{i}\right)=0, i=1, \ldots, n$

主循环$t=1: T$

1. 利用策略$\pi$选取某个动作$a$
2. 获取收益:$r_{t}=\operatorname{Bandit}(a)$
3. 更新计数器:$N(a):=N(a)+1$
4. 更新估值:$Q(a):=Q(a)+\frac{1}{N(a)}\left[r_{t}-Q(a)\right]$

收益估计是期望收益和采样次数的关系，更新估值时。

• 普通算法：将所有数求和再除以次数

  $Q_{n}\left(a^{i}\right)=\frac{r_{1}+r_{2}+\cdots+r_{n-1}}{n-1}$

  缺点是每次更新的空间复杂度是$O(n)$

• 增量实现

  $Q_{n+1}\left(a^{i}\right):=\frac{1}{n} \sum_{i=1}^{n} r_{i}=\frac{1}{n}\left(r_{n}+\frac{n-1}{n-1} \sum_{i=1}^{n-1} r_{i}\right)=\frac{1}{n} r_{n}+\frac{n-1}{n} Q_{n}=Q_{n}+\frac{1}{n}\left(r_{n}-Q_{n}\right)$ 误差项:$\Delta_{n}^{i}$

  空间复杂度为$O(1)$

以下内容维护中，编写未完成。

序列决策任务中的一个基本问题是基于目前策略获取最优收益还是尝试不同的决策

• Exploitation 执行能够获得最优收益的决策
• Exploration 尝试更多可能的决策，不一定会是最优收益，可能发现更好的策略

策略探索的一些原则

• 朴素方法 (Naive Exploration)

  添加策略噪声,e-greedy

• 积极初始化 (Optimistic Initialization)

• 基于不确定性的度量 (Uncertainty Measurement)

  尝试具有不确定收益的策略，可能带来更高的收益

• 概率匹配 (Probability Matching)

  基于概率选择最佳策略

• 状态搜索 (state Searching)

  探索后续状态可能带来更高收益的策略

收益（反馈）函数分布:$\mathcal{R}\left(r \mid a^{i}\right)=\mathbb{P}\left(r \mid a^{i}\right)$