Bandit Note（进行中）

Introduction

基本术语：

learner、player，决策者、玩家
environment，环境
horizon，决策周期
action，动作、决策、选择
reward，奖励
policy，策略
regret，悔恨

玩家在$n$轮决策周期内进行游戏，在每一轮$t\in[n]$中，玩家从给定动作集合$\mathcal{A}$中选择动作$A_t$，环境根据对应动作给出奖励$X_t\in\mathbb{R}$。

玩家每轮的决策$A_t$只能依赖于历史信息$H_{t-1}=(A_1,X_1,\cdots,A_{t-1},X_{t-1})$，策略是指通过历史信息来选择动作，从$H_{t-1}$到$A_t$的映射，玩家的目的是每一轮选择合适的决策，使得$n$轮之后的最大可能累计奖励最大，即$\sum_{t=1}^nX_t$。

用悔恨来评估一个玩家的表现，玩家相对策略$\pi$的悔恨是指，在$n$轮决策中，使用策略$$的期望奖励和玩家可以获得的期望奖励之差。策略集合$$的悔恨指任意策略$$所产生的最大悔恨。

策略集合$\Pi$通常被称为competitor class（暂时没有想到好的翻译）。也有另一种表述，对于competitor class中最好的策略，悔恨刻画了玩家的表现。我们通常是在一个足够大到可以包含任意环境$\mathcal{E}$的最优策略的策略集合$\Pi$上来衡量悔恨。在这种情况下，悔恨度量了玩家相对于最优策略的损失。

最坏情况悔恨，worst-case regret，是指对于所有可能的环境中，可能会出现的最大的悔恨。

bandit的一个核心问题就是研究悔恨随着轮数$n$的增长率，一个好的玩家可以得到次线性的悔恨，此处用$R_n$表示$n$轮后的悔恨。

bandit的框架有以下局限：

不能考虑未来影响，并不能对未来环境做出假设，未来并不会因为现在的决策而改变，如果需要考虑长期的计划，则需要考虑强化学习
假设了玩家可以实时观测到奖励
如果玩家是有战略的，则需要考虑博弈论相关的内容

Foundations of Probability

Stochastic Processes and Markov Chains

Stochastic Bandit

随机bandit是指分布$v=(P_a:a\in\mathcal{A})$的集合，在每一轮$t\in\{1,\cdots,n\}$，玩家选择一个动作$A_t\in\mathcal{A}$，环境从分布$P_{A_t}$中采样出奖励$X_t\in\mathbb{R}$返回给玩家，并通过序列$A_1,X_1,\cdots,A_n,X_n$来度量策略的好坏。

Concentration of Measure

马尔可夫不等式： \[ \mathbb{P}(|X|\geq \epsilon) \leq \frac{\mathbb{E}[|X|]}{\epsilon} \] 切比雪夫不等式： \[ \mathbb{P}(|X-\mathbb{E}[X]|\geq \epsilon)\leq \frac{\mathbb{V}[X]}{\epsilon^2} \]