agent

action

bandit 是强化学习的特例

example

随机bandit

regret： equivalent goal

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

the optimal value is

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

linear!! 有两种情况

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 尝试。

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

general case

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 is small we will require more tries to know that action 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 ), 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

and it’s zero if and only if for each , $} = 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 ), 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 go to zero. But at the same time, if all the 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 are the same, then another trivial regret bound is (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 . Using the notation, the regret is then just $\sum_i \Delta_i \mathbb{E}(latex-1584978965117.png)$, and bounding the ‘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 times. Recall further that the random variable has as its value the index of the machine chosen. We denote by $\chi(latex-1584978965127.png)$ the indicator random variable for the event . And remember that we use an asterisk to denote a quantity associated with the optimal action (e.g., is the empirical mean of the optimal action).

Indeed for any action , 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 . Now we’re just going to pull some number of plays out of that summation, keep it variable, and try to optimize over it. Since we might play the action fewer than 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 in round and we’ve already played at least 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 in round means that the upper bound for action exceeds the upper bound for every other action. In particular, this means its upper bound exceeds the upper bound of the best action (and 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 in round by $U_i(latex-1584978965333.png)$. Since this event must occur every time we pick action (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 exceeds that of the optimal machine, it is also the case that the maximum upper bound for action we’ve seen after the first trials exceeds the minimum upper bound we’ve seen on the optimal machine (ever). But on round 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 (except that it’s more than ). 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 the random variable for the empirical mean after playing action a total of times, and 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 to . This will become clear later, but it means we can replace with 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 . Likewise, (2) is the event that the empirical mean payoff of action is larger than the upper confidence bound, which also occurs with probability . We will see momentarily that (3) is impossible for a well-chosen (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 plus whatever the probability of (3) being true is. But as we said, we’ll pick to make (3) always false. Indeed depends on which action 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 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.

~ 最大后验概率

梯度bandit 算法

why not 梯度下降？

​ more general for RL

proof

// lemma 1 for homework