文章目录[隐藏]

利用与探索的两难
现实中的例子
两臂老虎机
三种类型
- 奖励模型
Decision making under uncertainty
action vs. reward
types of reward
types of rewards model
summary
- example
随机bandit

反馈：奖励

agent

action

bandit 是强化学习的特例

利用与探索的两难

短期与长期的对决

现实中的例子

两臂老虎机

三种类型

奖励模型

Decision making under uncertainty

action vs. reward

types of reward

types of rewards model

types of context

example

先验or后验

structured

global

summary

example

网飞展示广告

随机bandit

regret： equivalent goal

the value of an arbitrary action a is the mean reward for a (unknown):

the optimal value is

we care about total regret

example on a

In general, those values are unknown.

we must try actions to learn the action-values(explore), and prefer those that appear best(exploit).

action-value methods

methods that learn action-value estimates and nothing else

根据强大数定理。收敛于真实期望值。

counting regret

桥梁：计算total regret。变量为指示变量

亚当定理：得到lemma的结果

how to define a good learner.

linear!! 有两种情况

Greedy algorithm

每次取最高的期望

$\epsilon - greedy$

防止出现局部最优

proof of lower bound

incremental implementation

性能考量、实现在线学习

proof

bandit notation

进一步提高性能 Optimistic Initial values

All methods s ofar depends on which is 0 in this case. but we can do 5.

Initally bad case for more 尝试。

algorithm

DecayIng $\epsilon _{t} -Greedy$

insight：先降后升

performance comparison

## bandit algorithm lower bounds(depends on gaps)

Optimism in the face of uncertainty

which action to pick?

越未知需要探索

Upper Confidence Bound

hoeffding's inequality

general case

calculation

取bound得到置信区间的位置

UCB1

action 没有被充分的探索过，所以需要探索

上界探索

credit:https://jeremykun.com/2013/10/28/optimism-in-the-face-of-uncertainty-the-ucb1-algorithm/

Theorem: Suppose UCB1 is run as above. Then its expected cumulative regret $\mathbb{E}(latex-1584977927119.png)$ is at most$\displaystyle 8 \sum_{i : \mu_i < \mu^*} \frac{\log T}{\Delta_i} + \left ( 1 + \frac{\pi^2}{3} \right ) \left ( \sum_{j=1}^K \Delta_j \right )$

Okay, this looks like one nasty puppy, but it’s actually not that bad. The first term of the sum signifies that we expect to play any suboptimal machine about a logarithmic number of times, roughly scaled by how hard it is to distinguish from the optimal machine. That is, if $\Delta_i$ is small we will require more tries to know that action $i$ is suboptimal, and hence we will incur more regret. The second term represents a small constant number (the $1 + \pi^2 / 3$ part) that caps the number of times we’ll play suboptimal machines in excess of the first term due to unlikely events occurring. So the first term is like our expected losses, and the second is our risk.

But note that this is a worst-case bound on the regret. We’re not saying we will achieve this much regret, or anywhere near it, but that UCB1 simply cannot do worse than this. Our hope is that in practice UCB1 performs much better.

Before we prove the theorem, let’s see how derive the $O(latex-1584977927114.png)$ bound mentioned above. This will require familiarity with multivariable calculus, but such things must be endured like ripping off a band-aid. First consider the regret as a function $R(latex-1584977927125.png)$ (excluding of course $\Delta^*$ ), and let’s look at the worst case bound by maximizing it. In particular, we’re just finding the problem with the parameters which screw our bound as badly as possible, The gradient of the regret function is given by

$\displaystyle \frac{\partial R}{\partial \Delta_i} = - \frac{8 \log T}{\Delta_i2} + 1 + \frac{\pi2}{3}$

and it’s zero if and only if for each $i$ , $} = O(latex-1584977927124.png)$ . However this is a minimum of the regret bound (the Hessian is diagonal and all its eigenvalues are positive). Plugging in the $\Delta_i = O(latex-1584977927170.png)$ (which are all the same) gives a total bound of $O(latex-1584977927132.png)$ . If we look at the only possible endpoint (the $\Delta_i = 1$ ), then we get a local maximum of $O(latex-1584977927132.png)$ . But this isn’t the $O(latex-1584977927114.png)$ we promised, what gives? Well, this upper bound grows arbitrarily large as the $\Delta_i$ go to zero. But at the same time, if all the $\Delta_i$ are small, then we shouldn’t be incurring much regret because we’ll be picking actions that are close to optimal!

Indeed, if we assume for simplicity that all the $\Delta_i = \Delta$ are the same, then another trivial regret bound is $\Delta T$ (why?). The true regret is hence the minimum of this regret bound and the UCB1 regret bound: as the UCB1 bound degrades we will eventually switch to the simpler bound. That will be a non-differentiable switch (and hence a critical point) and it occurs at $\Delta = O(latex-1584977927136.png)$ . Hence the regret bound at the switch is $\Delta T = O(latex-1584977927304.png)$ , as desired.

Proving the Worst-Case Regret Bound

Proof. The proof works by finding a bound on $P_i(latex-1584978965148.png)$ , the expected number of times UCB chooses an action up to round $T$ . Using the $\Delta$ notation, the regret is then just $\sum_i \Delta_i \mathbb{E}(latex-1584978965117.png)$ , and bounding the $P_i$ ‘s will bound the regret.

Recall the notation for our upper bound $a(latex-1584978965147.png) = \sqrt{2 \log T / P_j(T)}$ and let’s loosen it a bit to $a(latex-1584978965148.png) = \sqrt{2 \log T / y}$ so that we’re allowed to “pretend” a action has been played $y$ times. Recall further that the random variable $I_t$ has as its value the index of the machine chosen. We denote by $\chi(latex-1584978965127.png)$ the indicator random variable for the event $E$ . And remember that we use an asterisk to denote a quantity associated with the optimal action (e.g., $\overline{x}^*$ is the empirical mean of the optimal action).

Indeed for any action $i$ , the only way we know how to write down $P_i(T)$ is as

$\displaystyle P_i(latex-1584978965149.png) = 1 + \sum_{t=K}^T \chi(I_t = i)$

The 1 is from the initialization where we play each action once, and the sum is the trivial thing where just count the number of rounds in which we pick action $i$ . Now we’re just going to pull some number $m-1$ of plays out of that summation, keep it variable, and try to optimize over it. Since we might play the action fewer than $m$ times overall, this requires an inequality.

$P_i(latex-1584978965206.png) \leq m + \sum_{t=K}^T \chi(I_t = i \textup{ and } P_i(t-1) \geq m)$

These indicator functions should be read as sentences: we’re just saying that we’re picking action $i$ in round $t$ and we’ve already played $i$ at least $m$ times. Now we’re going to focus on the inside of the summation, and come up with an event that happens at least as frequently as this one to get an upper bound. Specifically, saying that we’ve picked action $i$ in round $t$ means that the upper bound for action $i$ exceeds the upper bound for every other action. In particular, this means its upper bound exceeds the upper bound of the best action (and $i$ might coincide with the best action, but that’s fine). In notation this event is

$\displaystyle \overline{x}_i + a(latex-1584978965271.png) \geq \overline{x}* + a(P*(T), t-1)$

Denote the upper bound $\overline{x}_i + a(latex-1584978965272.png)$ for action $i$ in round $t$ by $U_i(latex-1584978965333.png)$ . Since this event must occur every time we pick action $i$ (though not necessarily vice versa), we have

$\displaystyle P_i(latex-1584978964873.png) \leq m + \sum_{t=K}T \chi(U_i(t-1) \geq U*(t-1) \textup{ and } P_i(t-1) \geq m)$

We’ll do this process again but with a slightly more complicated event. If the upper bound of action $i$ exceeds that of the optimal machine, it is also the case that the maximum upper bound for action $i$ we’ve seen after the first $m$ trials exceeds the minimum upper bound we’ve seen on the optimal machine (ever). But on round $t$ we don’t know how many times we’ve played the optimal machine, nor do we even know how many times we’ve played machine $i$ (except that it’s more than $m$ ). So we try all possibilities and look at minima and maxima. This is a pretty crude approximation, but it will allow us to write things in a nicer form.

Denote by $\overline{x}_{i,s}$ the random variable for the empirical mean after playing action $i$ a total of $s$ times, and $\overline{x}^*_s$ the corresponding quantity for the optimal machine. Realizing everything in notation, the above argument proves that

$\displaystyle P_i(T) \leq m + \sum_{t=K}T \chi \left ( \max_{m \leq s < t} \overline{x}{i,s} + a(s, t-1) \geq \min{0 < s' < t} \overline{x}*_{s'} + a(s', t-1) \right )$

Indeed, at each $t$ for which the max is greater than the min, there will be at least one pair $s,s'$ for which the values of the quantities inside the max/min will satisfy the inequality. And so, even worse, we can just count the number of pairs $s, s'$ for which it happens. That is, we can expand the event above into the double sum which is at least as large:

$\displaystyle P_i(T) \leq m + \sum_{t=K}T \sum_{s = m}{t-1} \sum_{s' = 1}{t-1} \chi \left ( \overline{x}_{i,s} + a(s, t-1) \geq \overline{x}*_{s'} + a(s', t-1) \right )$

We can make one other odd inequality by increasing the sum to go from $t=1$ to $\infty$ . This will become clear later, but it means we can replace $t-1$ with $t$ and thus have

$\displaystyle P_i(T) \leq m + \sum_{t=1}\infty \sum_{s = m}{t-1} \sum_{s' = 1}{t-1} \chi \left ( \overline{x}_{i,s} + a(s, t) \geq \overline{x}*_{s'} + a(s', t) \right )$

Now that we’ve slogged through this mess of inequalities, we can actually get to the heart of the argument. Suppose that this event actually happens, that $\overline{x}{i,s} + a(s, t) \geq \overline{x}^*{s'} + a(s', t)$ . Then what can we say? Well, consider the following three events:

(1) $\displaystyle \overline{x}*_{s'} \leq \mu* - a(s', t)$
(2) $\displaystyle \overline{x}_{i,s} \geq \mu_i + a(latex-1584978965039.png)$
(3) $\displaystyle \mu^* < \mu_i + 2a(s, t)$

In words, (1) is the event that the empirical mean of the optimal action is less than the lower confidence bound. By our Chernoff bound argument earlier, this happens with probability $t^{-4}$ . Likewise, (2) is the event that the empirical mean payoff of action $i$ is larger than the upper confidence bound, which also occurs with probability $t^{-4}$ . We will see momentarily that (3) is impossible for a well-chosen $m$ (which is why we left it variable), but in any case the claim is that one of these three events must occur. For if they are all false, we have

$\displaystyle \begin{matrix} \overline{x}{i,s} + a(s, t) \geq \overline{x}^*{s'} + a(s', t) & > & \mu^* - a(s',t) + a(s',t) = \mu^* \ \textup{assumed} & (1) \textup{ is false} & \ \end{matrix}$

and

$\begin{matrix} \mu_i + 2a(s,t) & > & \overline{x}{i,s} + a(s, t) \geq \overline{x}^*{s'} + a(s', t) \ & (2) \textup{ is false} & \textup{assumed} \ \end{matrix}$

But putting these two inequalities together gives us precisely that (3) is true:

$\mu^* < \mu_i + 2a(s,t)$

This proves the claim.

By the union bound, the probability that at least one of these events happens is $2t^{-4}$ plus whatever the probability of (3) being true is. But as we said, we’ll pick $m$ to make (3) always false. Indeed $m$ depends on which action $i$ is being played, and if $s \geq m > 8 \log T / \Delta_i^2$ then $2a(latex-1584978965191.png) \leq \Delta_i$ , and by the definition of $\Delta_i$ we have

$\mu^* - \mu_i - 2a(latex-1584978965195.png) \geq \mu^* - \mu_i - \Delta_i = 0$ .

Now we can finally piece everything together. The expected value of an event is just its probability of occurring, and so

$\displaystyle \begin{aligned} \mathbb{E}(P_i(T)) & \leq m + \sum_{t=1}\infty \sum_{s=m}t \sum_{s' = 1}t \textup{P}(\overline{x}_{i,s} + a(s, t) \geq \overline{x}*_{s'} + a(s', t)) \ & \leq \left \lceil \frac{8 \log T}{\Delta_i2} \right \rceil + \sum_{t=1}\infty \sum_{s=m}t \sum_{s' = 1}t 2t{-4} \ & \leq \frac{8 \log T}{\Delta_i2} + 1 + \sum_{t=1}\infty \sum_{s=1}t \sum_{s' = 1}t 2t{-4} \ & = \frac{8 \log T}{\Delta_i2} + 1 + 2 \sum_{t=1}\infty t^{-2} \ & = \frac{8 \log T}{\Delta_i2} + 1 + \frac{\pi2}{3} \ \end{aligned}$

The second line is the Chernoff bound we argued above, the third and fourth lines are relatively obvious algebraic manipulations, and the last equality uses the classic solution to Basel’s problem. Plugging this upper bound in to the regret formula we gave in the first paragraph of the proof establishes the bound and proves the theorem.