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

1、introduction

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

• Exploitation：利用当前已知信息做决策
• Exploration：探索未知空间获取更多信息

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

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

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

• 朴素探索(Naive Exploration): 在贪婪搜索的基础上增加一个Ɛ以实现朴素探索；
• 乐观初始估计(Optimistic Initialization): 优先选择当前被认为是最高价值的行为，除非新信息的获取推翻了该行为具有最高价值这一认知；
• 不确定优先(Optimism in the Face of Uncertainty): 优先尝试不确定价值的行为；
• 概率匹配（Probability Matching): 根据当前估计的概率分布采样行为；
• 信息状态搜索(Information State Search): 将已探索的信息作为状态的一部分联合个体的状态组成新的状态，以新状态为基础进行前向探索。
• 状态动作探索State-action exploration：系统地探索状态和动作空间，类似于查表法
• 参数探索Parameter exploration：
  • 动作选择遵照策略\(\pi (A|S,u)\)
  • 每隔一段时间，更新策略参数
  • 优点：连续的探索
  • 缺点：对状态/动作空间不直观

2、多臂赌博机 Multi-Armed Bandits

简介

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

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

线性和次线性的regret

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

• 曲线线性增长，表明
  • 算法停止探索
  • 算法卡在局部最优

2.1 朴素探索 native exploration

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

Solution：乐观初始化 Optimistic initialisation

Solution：选择策略让\(\epsilon\)递减

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

相关概念

总后悔值下限 lower bound

霍夫丁不等式 Hoeffding's inequality

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

UCB可以被应用到：

• 伯恩斯坦 不等式
• 经验伯恩斯坦 不等式
• 切尔诺夫 不等式
• azuma 不等式

贝叶斯 Bayesian bandits

贝叶斯UCB

• 计算方法：

2.1 概率匹配

特点：

• 面对不确定性时，概率匹配是最优的
  • 不确定行动，可能获取最大值
• 无法得到解析的后验值

2.2 Thompson Sampling

2.3 信息状态空间搜索 Information state search

Value information

Value 可以指导 动作性选择

评价 value of information

• 预算，获取信息的成本
  • 如果次数少，基于目前的选择；选择机会多，倾向于探索
  • 长期的奖励 由于 即刻 奖励
• 在不确定的情况下，信息增益高，如果什么都知道了，不需要获取信息
• 如果我们知道更多信息，就可以最优的平衡 利用 和 探索

信息状态空间 Information state space

Gittins indices for 贝叶斯赌博机

总结

3、语境赌博机 Contextual Bandits

introduction

线性 UCB

线性回归：

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

线性 UCB

几何解释：

求解线性UCB

4、MDPs

乐观初始化： model-free RL

Bayesian model-based RL

汤姆逊采样：model-based RL

Bayes adaptive MDPs