多臂老虎机问题 MAB

一个有K个拉杆的老虎机，拉动每一个拉杆都有对应的概率R获得奖励。目标是在操作T次拉杆后获得的奖励最大

可以这样描述：该问题可以表示为一个元组<A,R>,其中：

• A为动作集合，，由于有K个拉杆，动作空间就是集合${a_1,…a_K}$
• R为奖励概率分布，拉动每一根拉杆的动作a都对应一个奖励的概率分布$R(r｜a)$，不同拉杆奖励不同

每个时间步只能拉动一个拉杆，则该任务的目标为最大化时间步T内累计奖励： \(\max \overset{T}{\underset{t=1}{\sum}}r_t,r_t\sim R(\cdot｜a_t)\)

• 期望奖励$Q(a)$：$E_{r\sim R(\cdot

  a)}[r]$

• 最优期望奖励$Q^*=\max_{a\in A}Q(a)$
• 懊悔$R(a)=Q^*-Q(a)$
• 累计懊悔$\sigma_R=\overset{T}{\underset{t=1}{\sum}}R(a_t)$

MAB问题等价位最小化累计懊悔

估值期望奖励：可以采用迭代法，即 \(Q_k=\frac{1}{k}\sum^k_{i=1}r_i = Q_{k-1}+\frac{1}{k}[r_k-Q_{k-1}]\)

$\epsilon$ - 贪心算法

一种平衡探索（Exploration）和利用（Exploitation）的简单策略。算法在每个时间步$t$选择动作$a_t$的规则如下：

$ a_t = \begin{cases} \underset{a \in A}{\arg\max} \ Q_t(a) & \text{以概率 } 1-\epsilon
\text{从A中随机选择一个动作} & \text{以概率 } \epsilon \end{cases} $

• $Q_t(a)$: 在时间$t$时，对动作$a$的价值估计（即期望奖励）。
• 利用 (Exploitation): 以 $1-\epsilon$ 的概率，选择当前看来奖励最高的动作。这能充分利用已知的信息来获取最大回报。
• 探索 (Exploration): 以 $\epsilon$ 的概率，随机选择一个动作。这使得算法有机会探索未知的动作，可能会发现更好的选择，避免陷入局部最优。

上置信界算法 (UCB)

UCB算法对不确定性高的动作持乐观态度，它会给那些被选择次数较少的动作一个额外的“探索奖励”，鼓励算法去尝试它们。选择动作的准则是最大化预估价值和不确定性之和。

$ a_t = \underset{a \in A}{\arg\max} \left[ Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} \right] $

• $Q_t(a)$: 动作$a$的当前平均奖励，代表“利用”。
• $c \sqrt{\frac{\ln t}{N_t(a)}}$: 置信区间的上界，代表“探索”。
  • $t$: 当前的总试验次数。
  • $N_t(a)$: 动作$a$到目前为止被选择的次数。
  • $c$: 探索常数，用于调节探索的权重。$c>0$，c越大越偏向于探索。

核心思想: 当一个动作被选择的次数$N_t(a)$越少，其不确定性项（公式右侧）的值就越大，从而增加了它被选中的机会。随着试验次数的增加，所有动作都会被充分探索，最终算法会收敛到最优动作。

汤普森采样算法

该算法通常利用Beta分布为动作的奖励概率建模。Beta分布是一个定义在(0, 1)区间的连续概率分布，由两个参数$\alpha 、\beta$控制其形状，非常适合为如“成功/失败”这类事件的概率进行建模。

• 核心思想: 算法假设每个拉杆的奖励概率服从一个特定的概率分布，然后根据这个分布进行采样，选择采样中奖励最大的动作。这可以看作是一种蒙特卡卡罗方法，用于估计所有拉杆中产生最高奖励的概率。

• 算法流程:

  1. 分布建模: 我们通常使用Beta分布对每个动作的奖励概率进行建模。假设一个动作被执行了 $N$ 次，其中 $S$ 次成功（奖励为1），$F$ 次失败（奖励为0），那么该动作的奖励概率就服从参数为 $B(S+1, F+1)$ 的Beta分布。
  2. 采样: 在每个时间步，为每个动作（每个拉杆）的Beta分布进行一次采样，得到一组奖励样本。
  3. 选择: 选择样本中奖励值最大的动作并执行。
  4. 更新: 根据执行动作后得到的实际奖励（1或0），更新对应动作的Beta分布参数。如果奖励为1，则 $S \leftarrow S+1$；如果奖励为0，则 $F \leftarrow F+1$。

马尔可夫决策过程

• 马尔可夫性质：下一个状态只取决于当前状态，而不会受到过去状态的影响的性质

• 马尔可夫过程：具有马尔可夫性质的随机过程，也被称为马尔可夫链，用元组$<S,P>$表示

• 状态转移矩阵：P，每行/每列的和为1。$p_{ij}=P(s_j

  s_i)$

• 马尔可夫奖励过程：在马尔可夫过程基础上加入奖励函数r和折扣因子$\gamma$，表示为$<S,P,r,\gamma>$
  • $S$：有限状态集合
  • $P$：状态转移矩阵
  • $r$：奖励函数
  • $\gamma$：折扣因子，$0\sim 1$范围，用于形容远期利益和近期利益哪个大，接近1更关注远期
• 回报：所有奖励衰减之后的和 \(G_t = R_t+\gamma R_{t+1}+\gamma^2 R_{t+2}+...=\sum_{k=0}^\infty \gamma^kR_{t+k}\)

马尔可夫奖励过程 MRP

即在马尔可夫过程基础上加入奖励函数$r$和折扣因子$\gamma$。

• 回报：在马尔可夫奖励过程中，从$t$时刻$S_t$装题啊开始到最终状态时，所有奖励的衰减之和。

• 价值：一个状态期望的回报
• 价值函数：输入为某个状态，输出为该状态的价值

贝尔曼方程： \(V(s)=r(s)+\gamma\sum_{s'\in S}p(s'|s)V(s')\)

将所有价值和奖励函数写成一个列向量，可以将贝尔曼方程表示为矩阵形式：

矩阵运算求得解析解：$V=(I-\gamma P)^{-1}R$。计算复杂度较高，因此只使用很小的马尔可夫奖励过程

马尔可夫决策过程 MDP

• 策略： $\pi(a

  s) = P(A_t=a

  S_t=s)$

• 确定性策略/随机性策略：每一个状态只输出一个确定/不确定的动作
• 状态价值函数： \(V^{\pi}(s) = E_\pi [G_t|S_t=s]\)
• 动作价值函数； \(Q^\pi(s|a)=E_\pi[G_t|S_t=s,A_t=a]\)

在策略$\pi$中，状态的价值等于该状态下所有动作的概率乘动作价值的和

在策略$\pi$中，状态s下采取动作a的价值等于即时奖励加上经过衰减后所有可能的下一状态转移概率与价值的乘积

• 贝尔曼期望方程；

  • 状态价值函数 (state-value function) V(s): \(V^{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a|s) \left(r(s,a)+\gamma \sum_{s', r} p(s'| s, a) V^{\pi}(s')\right)\)

  • 动作价值函数 (action-value function) Q(s, a): \(Q^{\pi}(s, a) = r(s,a) +\gamma \sum_{s'\in S} p(s', r | s, a) \sum_{a' \in \mathcal{A}} \pi(a'|s') Q^{\pi}(s', a')\)

计算状态价值函数时，先将其视为一个MRP问题，对于策略的每一个动作的概率看作成一个状态转移概率。求得V后用上式再求Q

蒙特卡洛算法

这里放一段动作选择代码（按照不同动作概率随机选取动作）

for a_opt in A:
    temp += Pi.get(join(s, a_opt), 0)
    if temp > rand:
        a = a_opt
        r = R.get(join(s, a), 0)
        break
rand, temp = np.random.rand(), 0

占用度量

• 状态访问分布 $\nu^\pi(s)$：策略 $\pi$ 与 MDP 交互时访问状态 $s$ 的概率
  \(\nu^\pi(s) = (1-\gamma)\sum_{t=0}^\infty \gamma^t P_t^\pi(s)\)
  • $P_t^\pi(s)$：时刻 $t$ 状态为 $s$ 的概率（$P_0^\pi=\nu_0$ 初始状态分布）
  • $(1-\gamma)$：归一化因子

• 占用度量 $\rho^\pi(s,a)$：策略 $\pi$ 访问状态-动作对 $(s,a)$ 的概率
  \(\rho^\pi(s,a) = (1-\gamma)\sum_{t=0}^\infty \gamma^t P_t^\pi(s)\pi(a|s)\)

  \[\rho^\pi(s,a) = \nu^\pi(s) \cdot \pi(a|s)\]

1. 策略等价定理
   若两策略 $\pi_1, \pi_2$ 满足 $\rho^{\pi_1} = \rho^{\pi_2}$，则它们在访问过的状态上成比例：
   \(\pi_1 / \pi_2 \quad \text{(在访问过的状态上成立)}\)

2. 策略恢复定理
   对合法占用度量 $\rho$（存在策略能生成该度量），可唯一恢复策略：
   \(\pi_\rho(a|s) = \frac{\rho(s,a)}{\sum_{a'}\rho(s,a')}\)

   • 分母 $\sum_{a’}\rho(s,a’)$ 等价于状态访问度量 $\nu(s)$

最优策略

计作$\pi^(s)$,且$V^(s)=\underset{\pi}{\max}V^\pi(s)$

最优状态价值函数和最优动作价值函数之间的关系为：

• 贝尔曼最优方程：

• 新章
  机器人机构学笔记