Tolshao
Go back

强化学习笔记9：探索和利用 exploration and exploitation

1、introduction

本章的主题是关于利用和探索的矛盾：

最佳的策略是用长期的眼光来看，放弃短期高回报 获取足够策略是让策略变成全局最优的必要条件

几个基本的探索方法： 主要分三类：

  1. 随机
  2. 基于不确定性
  3. 信息状态空间

2、多臂赌博机 Multi-Armed Bandits

简介

一个赌徒面前有N个赌博机,事先他不知道每台赌博机的真实盈利情况,他如何根据每次玩赌博机的结果来选择下次拉哪台或者是否停止赌博,来最大化自己的从头到尾的收益. 多臂赌博机

将MDP简化为⟨A,R⟩\langle \mathcal A,\mathcal R \rangle

后悔值 Regret

total Regret的表达方式

将上页的后悔价值函数表示为 计数 和 gap 的乘积

Lt=E[∑τ=1tV∗−Q(aτ)]=∑a∈AE[Nt(a)](V∗−Q(a))=∑a∈AE[Nt(a)]Δa\begin{aligned} L_{t} &=\mathbb{E}\left[\sum_{\tau=1}^{t} V^{*}-Q\left(a_{\tau}\right)\right] \\ &=\sum_{a \in \mathcal{A}} \mathbb{E}\left[N_{t}(a)\right]\left(V^{*}-Q(a)\right) \\ &=\sum_{a \in \mathcal{A}} \mathbb{E}\left[N_{t}(a)\right] \Delta_{a} \end{aligned}

好的算法让大gap对应的计数最小，但问题是，gaps未知？？？

线性和次线性的regret

因为总计后悔值，是累加计算，只要有gap，就会随着时间步增长

-w449

2.1 朴素探索 native exploration

greedy：卡在局部最优，总后悔线性增长

at∗=argmax⁡a∈AQ^t(a)a^*_t = \underset{a\in A}{\operatorname {argmax}} \hat Q_t(a)

Greedy 可能卡在永远次优动作，总regret随时间步线性增长

Solution：乐观初始化 Optimistic initialisation

理论上，还应该是total regret 线性增长，实际效果却很好，采用递归MC更新Q值

\hat{Q}_{t}\left(a_{t}\right)=\hat{Q}_{t-1}+\frac{1}{N_{t}\left(a_{t}\right)}\left(r_{t}-\hat{Q}_{t-1}\right)$$ 操作步骤： - 将V值初始化为最大值，$Q(a)= r_{max}$ - act greedily $$A_t = \underset{a\in A}{\operatorname {argmax}} Q_t(a)$$ - 鼓励探索未知values 但是仍未能避免不幸的采样导致卡在次优 ### $\epsilon-greedy$：小概率随机动作，累加后悔值，导致总后悔值随时间步线性增长 - 特性：永远保持探索: - 概率（1-$\epsilon$）$A= \underset{a\in A}{argmax}Q(a)$ - 概率（$\epsilon$）随机动作 - $\epsilon$保证了最小的regret，满足

l_t \geq \frac{\epsilon}{A}\sum_{a\in A}\Delta_a

$\epsilon-greedy$ 仍然是线性总regret，因为会$\epsilon$随机采样到大gap ### **Solution**：选择策略让$\epsilon$递减 核心思想：假设我们现在知道每一个行为的最优价值$V^*$，那么我们可以根据行为的价值计算出所有行为的$\Delta_a$ 。可设置为：如果一个行为的差距越小，则尝试该行为的机会越多；如果一个行为的差距越大，则尝试该行为的几率越小。数学表达如下： 策略如下：

\begin{array}{l} c>0 \ d=\min {a \mid \Delta{a}>0} \Delta_{i} \ \epsilon_{t}=\min \left{1, \frac{c|\mathcal{A}|}{d^{2} t}\right} \end{array}$$

小结：

2.2 不确定性优先 optimism in the face of uncertainty

相关概念

总后悔值下限 lower bound

当有噪声干扰，或者表现具有相似性，无法从反馈信息直接判断动作好坏

可以用gapΔagap\Delta_a， 和分布的相似程度KL散度 KL(Ra∣∣Ra∗)KL(R^a||R^a*)，来计算总后悔值的下限：

定理：（Lai and robbins） 存在一个总后悔值的下限，没有哪一个算法能够做得比这个下限更好 渐进总regret 至少是步数的对数 lim⁡t→∞Lt≥log⁡t∑a∣Δa>0ΔaKL(Ra∣∣Ra∗)\lim _{t \rightarrow \infty} L_{t} \geq \log t \sum_{a \mid \Delta_{a}>0} \frac{\Delta_{a}}{K L\left(\mathcal{R}^{a}|| \mathcal{R}^{a^{*}}\right)}

置信上限 Upper confidence bound

为什么要分析置信上限，通过分析上限，可以将表现有潜力的动作选出 上限的选取，是基于概率的，选择要包容95%、99%的置信区间

at=argmax⁡a∈A(Q^t(a)+U^t(a))a_t = \underset{a\in A}{\operatorname {argmax}}\left(\hat Q_t(a) + \hat U_t(a)\right)

小结：随仿真进行，提高置信度

霍夫丁不等式 Hoeffding’s inequality

提供了置信上限的计算方法，要求先对数据进行缩放，缩放到[0,1] -w422

将不等式应用到奖励赌博机中

P[Q(a)>Q^t(a)+Ut(a)]≤e−2Nt(a)Ut(a)2\mathbb{P}\left[Q(a)>\hat{Q}_{t}(a)+U_{t}(a)\right] \leq e^{-2 N_{t}(a) U_{t}(a)^{2}}

利用霍夫丁不等式计算UCB
e−2Nt(a)Ut(a)2=pUt(a)=−log⁡p2Nt(a)\begin{aligned} e^{-2 N_{t}(a)} U_{t}(a)^{2} &=p \\ U_{t}(a) &=\sqrt{\frac{-\log p}{2 N_{t}(a)}} \end{aligned}

实际操作过程中，随着采样点增多，我们希望对Q的估计越来越确信，所以逐步减少p值 通过降低p，可以获取更多奖励，随着仿真进行，降低p值，e.g. p=t−4p = t^{-4} Ut(a)=2log⁡tNt(a)U_{t}(a)=\sqrt{\frac{2 \log t}{N_{t}(a)}}

UCB1

利用霍夫丁不等式，let p=t−4p = t^{-4} UCB1算法如下： at=argmax⁡a∈AQ(a)+2log⁡tNt(a)a_{t}=\underset{a \in \mathcal{A}}{\operatorname{argmax}} Q(a)+\sqrt{\frac{2 \log t}{N_{t}(a)}}

定理： UCB算法趋向于对数渐进 总regret lim⁡t→∞Lt≤8log⁡t∑a∣Δa>0Δa\lim _{t \rightarrow \infty} L_{t} \leq 8 \log t \sum_{a \mid \Delta_{a}>0} \Delta_{a}

效果对比： -w843

UCB可以被应用到：

贝叶斯 Bayesian bandits

与多臂赌博机不同，贝叶斯赌博机中，我们期望通过episode 的经验构建动作-奖励概率函数 和 Q值函数，用后验估计来指导最优动作的选取

贝叶斯UCB

at=argmax⁡a∈Aμa+cσa/N(a)a_{t}=\underset{a\in A}{\operatorname {argmax}} \mu_{a}+c \sigma_{a} / \sqrt{N(a)}

2.1 概率匹配

选择动作：按照最有动作的概率挑选动作

π(a∣ht)=P[Q(a)>Q(a′),∀a′≠a∣ht]\pi\left(a \mid h_{t}\right)=\mathbb{P}\left[Q(a)>Q\left(a^{\prime}\right), \forall a^{\prime} \neq a \mid h_{t}\right]

按照纵坐标的大小去选

-w416

特点：

2.2 Thompson Sampling

基于概率匹配的方法

π(a∣ht)=P[Q(a)>Q(a′),∀a′≠a∣ht]=ER∣ht[1(a=argmax⁡a∈AQ(a))]\begin{aligned} \pi\left(a \mid h_{t}\right) &=\mathbb{P}\left[Q(a)>Q\left(a^{\prime}\right), \forall a^{\prime} \neq a \mid h_{t}\right] \\ &=\mathbb{E}_{\mathcal{R} \mid h_{t}}[\mathbf{1}(a=\underset{a \in \mathcal{A}}{\operatorname{argmax}} Q(a))] \end{aligned}

操作步骤：

  1. 使用贝叶斯法则计算后验分布p[R∣ht]p[R|h_t]
  2. 从后验分布中采样 R 值，根据奖励值期望，计算动作价值函数
  3. 选取最优动作，即可最大化Q(a) as at=argmax⁡a∈AQ(a)a_t = \underset{a\in A}{\operatorname{argmax}}Q(a)

汤姆森采样，同样满足Lai robbins 下限

采样在序列问题中，表现的很好，因为采样打破了序列的排列造成的干扰。

Value information

Value 可以指导 动作性选择

评价 value of information

信息状态空间 Information state space

信息状态空间包括了状态在内的历史信息，总结归纳出的信息，可以通过状态空间的信息预估奖励、下时刻的状态等

定义增强MDP M~\tilde {\mathcal M} as M~=⟨S~,A,P~,R,γ⟩\tilde{\mathcal M} = \langle \tilde S, A, \tilde P, R, \gamma \rangle

这是一个infinite MDP，因为空间无限，但是可以用RL解决

Solution for information state space bandits：

具体步骤

beta 分布，根据计数，更新后验估计的分布函数

  1. 从beta(αa,βa)beta(\alpha_a,\beta_a)先验分布开始
  2. 每一步选取动作，根据结果更新后验估计 for Ra\mathcal {R^a}
    • beta(αa+1,βa)beta(\alpha_a+1,\beta_a) if r = 0;
    • beta(αa,βa+1)beta(\alpha_a,\beta_a+1) if r = 1;
  3. 定义了状态转移函数P~\tilde P for 贝叶斯自适应MDP
  4. 信息空间对应beta(αa,βa)beta(\alpha_a,\beta_a)
  5. 每个状态转移 对应 一次贝叶斯模型更新

-w522

Gittins indices for 贝叶斯赌博机

贝叶斯自适应 MDP 可以用 动态规划 求解，被称作 【gittins index】 精确求解贝叶斯自适应MDP是非常棘手的，信息状态空间太大

更高效的解决方法是：使用simulation-based search - 对信息状态空间进行前向搜索 - 从当前状态开始，用simulation的方法

总结

3、语境赌博机 Contextual Bandits

introduction

线性 UCB

线性回归：

构建线性回归Q值 函数估计器，求解估计参数，在状态s下可以求得最优动作a -w546

线性 UCB

最小二乘回归，使用参数θ\theta，估计动作价值函数 同样，可以估计Q值的方差σθ2(s,a)\sigma^2_\theta (s,a)

定义UCB as， Uθ(s,a)=cσU_\theta (s,a) = c \sigma

几何解释：

-w566

求解线性UCB

-w559

4、MDPs

前述的利用/探索的规则，虽然是基于赌博机问题开发的，但是扩展到 full MDPs过程，同样有效

Agent，不根据最大的平均Q值来选择动作，根据概率分布推测的Q值上限来选择动作，不放过潜力股 但是，一般的Q值只是在某个策略下的Q值，最好能考虑策略的上限，然而这是非常难的

乐观初始化： model-free RL

乐观初始化： model-based RL

UCB：model-free RL

at=argmax⁡a∈AQ(st,a)+U(st,a)a_{t}=\underset{a \in \mathcal{A}}{\operatorname{argmax}} Q\left(s_{t}, a\right)+U\left(s_{t}, a\right) 
- 估计策略评估的不确定性，（简单）
- 在策略提高的过程中，忽略不确定性
at=argmax⁡a∈AQ(st,a)+U1(st,a)+U2(st,a)a_{t}=\underset{a \in \mathcal{A}}{\operatorname{argmax}} Q\left(s_{t}, a\right)+U_{1}\left(s_{t}, a\right)+U_{2}\left(s_{t}, a\right) 
- 估计策略评估的不确定性$U_1(s_t,a)$，（简单）
- **加上** 策略评估的不确定性$U_2(s_t,a)$，（复杂）

Bayesian model-based RL

汤姆逊采样：model-based RL

\begin{aligned} \pi\left(s, a \mid h_{t}\right) &=\mathbb{P}\left[Q^{*}(s, a)>Q^{*}\left(s, a^{\prime}\right), \forall a^{\prime} \neq a \mid h_{t}\right] \\ &=\mathbb{E}_{\mathcal{P}, \mathcal{R} \mid h_{t}}\left[\mathbf{1}\left(a=\underset{a \in \mathcal{A}}{\operatorname{argmax}} Q^{*}(s, a)\right)\right] \end{aligned}$$ - 使用贝叶斯法则去计算后验估计$p[P,R|h_t]$ - 从后验估计中采样MDP - 用规划方法求解最优价值函数$Q^*(s,a)$ - 从采样的MDP中，选取最有动作，$a_t = \underset{a\in A}{\operatorname{argmax}}Q^*(s_t,a)$ ## Bayes adaptive MDPs ### 信息空间搜索 in MDPs - MDPs 可以被增强为 带有信息空间的MDPs - 增强后的空间表示为$\langle S,\tilde S \rangle$ - S是MDP的原始状态 - $\tilde S$是静态的历史状态 - 每个动作造成一个转移 - 去新状态s'的概率$\mathcal P^a_{s,s'}$ - 去新的信息空间$\tilde{s'}$ - 定义MDP$\tilde M$ 表示为

\tilde M = \langle \tilde S, A \tilde P , R , \gamma \rangle

### 自适应贝叶斯 MDPs - 后验分布 for MDP model 是一个信息空间

\tilde S_t = \mathcal P[\mathcal P, R|h_t]$$

Share this post on:
Share this post via WhatsApp Share this post on Facebook Share this post on X Share this post via Telegram Share this post on Pinterest Share this post via email
Previous Post
强化学习笔记10：经典游戏示例 classic games
Next Post
解锁播放器的隐藏功能👀用过的都说好😎