Online Learning 3: Adversarial bandit learning with catastrophes

post by RyanCarey · 2016-11-14T22:58:01.000Z · LW · GW · 0 comments

Contents

    Setup
    Defining the agent's performance
    A proposed learning model
    Good surrogate performance implies good deployment performance
      Lemma 2
    Bounds  on estimation error
    A bound on surrogate regret
      Lemma 5
    A bound on sampling probabilities
      Lemma 6.
      Lemma 7.
    Completing the proof of Theorem 1
    Achieving sublinear regret and sublinear exploration
    Discussion
  References
None
No comments

Note: This describes an idea of Jessica Taylor’s.

In order to better understand how machine learning systems might avoid catastrophic behavior, we are interested in modeling this as an adversarial learning problem.

---

A major challenge with efficiently learning to avoid catastrophes is that the utility (or loss) function can take extremely negative values. This causes problems for standard online learning models, which often incur regret proportional to the difference between the maximum and minimum achievable utility.

In our last post, we explored how exploration-only bandit algorithms can be adapted to efficiently learn to avoid catastrophic actions. That model was oversimplified in a couple of ways. First, it provided a fixed distribution of examples to the learner. Second, it cleanly divides the learning process into an exploration phase, in which the learner can make many mistakes, and a subsequent deployment phase, in which the learner must select some near-optimal, non-catastrophic arm. In this post, we relax both of these assumptions. We use a learner that responds to a changing, adversarially-selected stream of examples. We do continue to allow the learner some exploration steps but the learner must choose when to use these to avoid catastrophic consequences. We don't achieve tight bounds, but we demonstrate that bandit learning systems can at least achieve sublinear regret using a sublinear number of exploration steps in an adversarial context. Similarly to our last post, we assume that the learner's beliefs about risks of catastrophe contain some grain of truth. Specifically, in this post, the learner has access to some overestimates of how frequently it should check for catastrophes, and sum of these estimates is not too high by more than a constant factor. We also assume the existence of some arm that has no risk of catastrophe.

The proofs in this post are somewhat long, and may be substantially changed with future work, so some readers may want to just read "Setup", "Defining the agent's performance", "A proposed learning model" and "Discussion".

Setup

Our model relies on some definitions:

• Let $I=\{I_1,I_2,...,I_K\}$ be a set of bandit arms.
• Let $R_t:I\mapsto [0,1]$ be the intrinsic reward function selected at time step $t$.
• Let $C_t:I\mapsto [0,1]$ be the intrinsic catastrophic risk function at time step $t$. We assume that there is some bandit arm that always avoids catastrophes: $$\exists i\in I\text{s.t.}\forall t{C}_t\left(i\right)=0$$
• Let $M_t\left(i\right):=R_t\left(I\right)-\frac{C_t\left(i\right)}{\tau }$ be the net payoff for the agent, where $\tau \in (0,1]$ is the risk-tolerance, which may be some very small number of order ${10}^{-20}$.
• Let $a_{t,i_t}:=min(\frac{C_t\left(i_t\right)}{z\tau },1)$ be the ideal sampling probability, where $z\in [1,\infty )$ is a parameter that specifies how much lost utility from catastrophes the learner tolerates.
• Let ${\hat{a}}_{t,i_t}\in [0,1]$ be some overestimate of the ideal sampling probability. The learner has access to this overestimate.
• Let $b_{t,i_t}\in [0,1]$ be the sampling probability that the learner selects for some time step.

On each time step, $1,2,...,T$, the learner performs two tasks: i) it selects an arm, and ii) it decides whether the step is an exploration step or a deployment step. Both of these decisions are carried out probabalistically.

To begin each time step $t$, the learner outputs a distribution over arms, $D\in \Delta I$. The learner also outputs a sampling probability $b_{t,i_t}$ to be used if each arm $i_t$ is selected. The adversary selects the intrinsic reward and catastrophic risk functions, $R_t$ and $C_t$ in response to $D$. Then, the learner's selected arm $i_t$ is drawn from $D$.

Next, a biased coin is flipped, with probability $b_{t,i_t}$ of heads, $F_t\sim \text{Bernoulli}\left(b_{t,i_t}\right)$. If it lands heads ($F_t=1$) then $t$ is an exploration step. This means that the learner observes the intrinsic reward $R_t\left(i_t\right)$ and risk $C_t\left(i_t\right)$ of its selected arm but receives no payoff. If the coin lands tails, $t$ it is a deployment step, the agent receives a payoff but does not observe it.

After $T$ of these time steps have passed, the hope is that our learning algorithm has achieved low regret and has used few exploration steps.

Defining the agent's performance

We define the number of exploration steps and the regret in turn.

The number of exploration steps is defined as ${\sum }_{t=1}^T{F}_t$.

Regret is defined relative to the best arm, $i^{\ast }$: $$i^{\ast }\in \underset{i^{\prime }\in I}{argmax}\sum _{t=1}^T{M}_t\left(i^{\prime }\right)$$

The regret for a series of arms $i_1,i_2,...,i_T$ is then: $$\begin{array}{cc}\text{Regret}\left(i^{\ast }\right)& :=\sum _{t=1}^T{M}_t\left(i^{\ast }\right)-\sum _{t=1}^{T}E\left[\right(1-F_t)\cdot M_t(i_t\left)\right]\\ & =\sum _{t=1}^T\left(M_t\right(i^{\ast })-(1-b_{t,i_t}\left)M_t\right(i_t\left)\right)\end{array}$$

To summarize, the learner only accumulates its net payoff from deployment steps but it is expected to come close to the maximum payoff that can be achieved using all time steps.

A proposed learning model

In designing a learning system for this kind of problem, a couple of difficulties arise. The first is that the surrogate loss function has an extremely large range. The net payoff function $M_t$ has range $[-\frac{1}{\tau },1]$, where $\tau \approx {10}^{-20}$ and so when bandit algorithms like Exp3 are applied to this learning problem, their regret will include an unacceptable factor of $1/\tau$. So $M_t$ is replaced with a surrogate loss function $S_t$, whose range is capped to $[-z,1]$:

$$S_t\left(i\right):=R_t\left(i\right)-min(\frac{C_t\left(i\right)}{\tau },z)$$

where $z\in [1,\infty )$ indicates how how much lost utility from catastrophes the learner tolerates.

The second difficulty is that if the learner observed $S_t$ on every time step, it would always output $b_{t,i_t}=1$, and it would use a linear number of exploration steps. To achieve a sublinear amount of exploration, the learner must instead use sampling probabilities $b_{t,i_t}$ that are sublinear in $T$ and use estimates of the surrogate problem, ${\hat{S}}_1\left(i\right),...,{\hat{S}}_T\left(i\right)$, such that:

$$\begin{array}{cc}{\hat{S}}_t\left(i\right)& :=F_t\frac{R_t\left(i\right)-min\left(\frac{1}{\tau }{C}_t\right(i),z)}{b_{t,i_t}}\end{array}$$ where $\gamma \in (0,1]$ is the base sampling rate. Note that this estimate depends on the sampling probabilities $b_{t,i_t}$, which in turn depends on the learner's selected arms, $i_t$.

The main result, which follows from Theorem 1, is that a bandit learner can achieve ($ϵ,\delta$)-optimal regret for any $\delta \in (0,1)$ where the error $ϵ$ and the number of exploration time steps are sublinear, and do not depend on the risk-tolerance, $\tau$.

**Theorem 1. ** Consider a learner that selects a sequence of arms $i_1,i_2,...,i_T$ using the Exp3 algorithm on some payoff functions ${\hat{S}}_1,...,{\hat{S}}_T$ using sampling probabilities $b_{1,i_1},b_{2,i_2},...,b_{T,i_T}$, such that: $$b_{t,i_t}:=min(max({\hat{a}}_{t,i_t},\gamma ),1)$$ where the learner uses an overestimate of the ideal sampling probability ${\hat{a}}_{t,i_t}\ge a_{t,i_t}$ whose sum exceeds the ideal sampling probabilities by some fixed constant $T\in [1,\infty )$: $$\sum _{t=1}^T{\hat{a}}_{t,i_t}\le H\sum _{t=1}^T{a}_{t,i_t}$$ where $H\ge 1$. Then, the learner's regret and exploration steps are probabalistically bounded: $$\begin{array}{cc}& \text{Pr}(\sum _{t=1}^T{F}_t\ge \zeta +\frac{H}{z}(2\alpha +\eta +T)\vee \sum _{t=1}^T(M_t\left(i^{\ast }\right)-(1-b_{t,i_t})M_t\left(i_t\right))\ge 2\alpha +\eta +\frac{2\alpha +\eta +T}{z})\\ & \le 2\exp \left(\frac{-{\gamma }^2{\alpha }^2}{2z^{2}T}\right)+\exp \left(\frac{-{\zeta }^2}{8T}\right)\end{array}$$ where $\eta =2\frac{(z+1)}{\gamma }\sqrt{(e-1)K\ln \left(K\right)T}$ where $\alpha >0$, $\zeta >0$, $\gamma \in (0,1]$ is the base sampling rate, $K$ is the number of bandit arm, and $z\in [1,\infty ]$ being amount of utility that the learner is prepared to lose from catastrophes.

In outline, our approach is to use the Exp3 adversarial bandit algorithm on the estimates ${\hat{S}}_1,...,{\hat{S}}_T$ of the surrogate loss function. We will begin by showing that the surrogate regret upper-bounds the actual regret (Lemma 2). We then quantify the error from approximating the surrogate regret (Lemmas 3, 4). To the estimation error, we add the regret from the Exp3 algorithm to obtain Lemma 5. To prove the bound on exploration steps, Theorem 2 is just a small extension.

Good surrogate performance implies good deployment performance

First, we need to show that $S_t$ is a good surrogate for $M_t$. Specifically, we show that the regret with $M_t$ is bounded by our regret with $S_t$.

Lemma 2

If a learner selects arms $i_1,...i_T$ and sampling probabilities $b_{1,i_1},...,b_{T,i_T}$ as described in Theorem 1, then, its regret will be no worse than the regret with with the surrogate $S_t$. $$\text{Regret}\left(i^{\ast }\right)=\sum _{t=1}^T\left(M_t\right(i_t)-(1-b_{t,i_t}\left)M_t\right(i^{\ast })\le \sum _{t=1}^T(S_t\left(i^{\ast }\right)-(1-b_{t,i_t})S_t\left(i_t\right)$$

Proof of Lemma 2. First, we can show that $(1-b_{t,i_t})M_t\left(i_t\right)=(1-b_{t,i_t})S_t\left(i_t\right)$. This is because if the catastrophic risk is ever too high, the learner will just take an exploration step.

If the catastrophic risk from some arm $i_t$ is unacceptably high, i.e. $\frac{C_t\left(i_t\right)}{\tau }>z$, then $b_{t,i_t}={\hat{a}}_{t,i_t}=a_{t,i_t}=1$, and so $(1-b_{t,i_t})=0$.

If the catastrophic risk is in the acceptable range, i.e. if $\frac{C_t\left(i_t\right)}{\tau }\le z$, then:

$$\begin{array}{cc}{M}_t\left(i_t\right)-S_t\left(i_t\right)& =\left(R_t\right(i_t)-\frac{C_t\left(i_t\right)}{\tau })-\left(R_t\right(i_t)-min(\frac{C_t\left(i_t\right)}{\tau },z))\\ & =0\end{array}$$

So for all time steps in $\{1,2,...,T\}$, $(1-b_{t,i_t})\left(M_t\right(i_t)-S_t(i_t\left)\right)=0$, so ${\sum }_{t=1}^T(1-b_{t,i_t})\left(M_t\right(i_t)-S_t(i_t\left)\right)=0$. It follows that: $$\sum _{t=1}^T(1-b_{t,i_t})M_t\left(i_t\right)=\sum _{t=1}^T(1-b_{t,i_t})S_t\left(i_t\right)$$

We must also show that ${\sum }_{t=1}^T{M}_t\left(i^{\ast }\right)\le {\sum }_{t=1}^T{S}_t\left(i^{\ast }\right)$. This is true because for all $i$, $S_t\left(i\right)\ge M_t\left(i\right)$. One can see that $M_t\left(i\right)-S_t\left(i\right)=min(\frac{C_t,\left(i\right)}{\tau },z)-\frac{C_t,\left(i^{\ast }\right)}{\tau }\le 0$.

It therefore follows that: $$\text{Regret}\left(i^{\ast }\right)=\sum _{t=1}^T\left(M_t\right(i^{\ast })-(1-b_{t,i_t}\left)M_t\right(i_t)\le \sum _{t=1}^T(S_t\left(i^{\ast }\right)-(1-b_{t,i_t})S_t\left(i_t\right))$$

◻

Bounds on estimation error

The next step is to bound the error that arises from estimating $S_t$ with ${\hat{S}}_t$.

Lemma 3 If a learner selects arms $i_1,...i_T$ and sampling probabilities $b_{1,i_1},...,b_{T,i_T}$ as described in Theorem 1, then:

$$\text{Pr}\left(\sum _{t^{\prime }=1}^t\right({\hat{S}}_{t^{\prime }}\left(i_t\right)-S_{t^{\prime }}\left(i_t\right))>\alpha )\le \exp \left(\frac{-{\gamma }^2{\alpha }^2}{2z^{2}t}\right)$$ where $\alpha >0$.

Proof of Lemma 3.

First, we show that ${\hat{S}}_t\left(i\right)$ is an unbiased estimate of $S_t\left(i\right)$. $$\begin{array}{cc}E\left[{\hat{S}}_t\right(i\left)\right]& =E\left[F_t\frac{R_t\left(i_t\right)-min\left(\frac{1}{\tau }{C}_t\right(i_t),z)}{b_{t,i_t}}\right]\\ & =b_{t,i_t}\frac{R_t\left(i\right)-min\left(\frac{1}{\tau }{C}_t\right(i_t),z)}{b_{t,i_t}}\\ & =S_t\left(i\right)\end{array}$$

Then, since ${\hat{S}}_t\left(i\right)$ is an unbiased estimate of $S_t\left(i\right)$, we can define the following martingale:

$$X_t:=\sum _{t^{\prime }=1}^t\left({\hat{S}}_{t^{\prime }}\right(i_{t^{\prime }})-S_{t^{\prime }}(i_{t^{\prime }}\left)\right)$$

Using the fact that $S_t\left(i_t\right)$ has range $[-z,1]$, we can bound $|X_t-X_{t-1}|$: $$\begin{array}{ccc}{X}_t-X_{t-1}& ={\hat{S}}_t\left(i_t\right)-S_t\left(i_t\right)& \\ & =(\frac{1}{b_{t,i_t}}{F}_t-1)S_t\left(i_t\right)& \\ \therefore |X_t-X_{t-1}|& \le max(|\frac{1}{b_{t,i_t}}-1|,|-1|)\cdot |-z|& \\ & \le max(\frac{1}{min(max({\hat{a}}_{t,i_t},\gamma ),1)}-1,1)\cdot z& \\ & \le max(\frac{1}{\gamma }-1,1)\cdot z& \\ & \le \frac{z}{\gamma }& (\gamma \in (0,1\left]\right)\end{array}$$

Azuma's inequality yields the result:

$$\text{Pr}\left(\sum _{t^{\prime }=1}^t\right({\hat{S}}_{t^{\prime }}\left(i_t\right)-S_{t^{\prime }}\left(i_t\right))>\alpha )\le \exp \left(\frac{-{\gamma }^2{\alpha }^2}{2z^{2}t}\right)$$ where $\alpha >0$. ◻

We will use the same argument to bound the estimation error when a best arm $i^{\ast }$ is repeatedly selected.

Lemma 4. Consider that learner selects arms $i_1,...i_T$ and sampling probabilities $b_{1,i_1},...,b_{T,i_T}$ as described in Theorem 1, and let $i^{\ast }\in {argmax}_{i^{\prime }\in I}{\sum }_{t=1}^T{M}_t\left(i^{\prime }\right)$ be a best arm. Then the estimate of the payoffs for the best arm can be bounded by:

$$\begin{array}{c}\text{Pr}\left(\sum _{t^{\prime }=1}^t\right(S_{t^{\prime }}\left(i^{\ast }\right)-{\hat{S}}_{t^{\prime }}\left(i^{\ast }\right)>\alpha )\le \exp \left(\frac{-{\gamma }^2{\alpha }^2}{2z^{2}t}\right)\end{array}$$ where $\alpha >0$.

Proof of Lemma 4.

The proof is similar to Lemma 3. Since ${\hat{S}}_{t^{\prime }}\left(i^{\ast }\right)$ is an unbiased estimate of $S_{t^{\prime }}\left(i^{\ast }\right)$, we have the martingale $Y_t={\sum }_{t^{\prime }=1}^t\left(S_{t^{\prime }}\right(i^{\ast })-{\hat{S}}_{t^{\prime }}(i^{\ast }\left)\right)$. As in Lemma 3, this martingale is bounded by $|Y_t-Y_{t-1}|\le \frac{z}{\gamma }$. The application of Azuma's inequality yields the result.◻

A bound on surrogate regret

In order to prove Theorem 1, we will need to show that the Exp3 algorithm achieves low regret with respect to ${\hat{S}}_t$.

Its regret guarantee states that an Exp3 learner that selects some arms $i_1,i_2,...,i_T$ on some payoff functions ${\hat{S}}_1,...,{\hat{S}}_T$ that have range $[\frac{-z}{\gamma },\frac{1}{\gamma }]$ will have regret bounded as [1]:

$$\begin{array}{cc}\underset{i^{\prime }\in I}{sup}\sum _{t=1}^T\left({\hat{S}}_t\right(i^{\prime })-{\hat{S}}_t(i_t\left)\right)& \le 2(\frac{1}{\gamma }-\frac{-z}{\gamma })\sqrt{e-1}\sqrt{TK\ln K}\\ & \le 2\frac{(z+1)}{\gamma }\sqrt{e-1}\sqrt{TK\ln K}\end{array}$$

Next, we show that the Exp3 algorithm will perform well on the surrogate problem.

Lemma 5

If a learner selects arms $i_1,...i_T$ and sampling probabilities $b_{1,i_1},...,b_{T,i_T}$ as described in Theorem 1, then its performance in on the surrogate problem will be probabalistically bounded: $$\text{Pr}\left(\sum _{t=1}^T\right(S_t\left(i^{\ast }\right)-S_t\left(i_t\right))\ge 2\alpha +\eta )\le 2\exp \left(\frac{-{\gamma }^2{\alpha }^2}{2z^{2}T}\right)$$ where $\eta =2\frac{(z+1)}{\gamma }\sqrt{(e-1)K\ln \left(K\right)T}$, and $\alpha >0$.

Proof of Lemma 5. Using the union bound, we have that: $$ \begin{aligned} & \text{Pr}\left(\sum_{t=1}^T (S_{t}(i^) - S_{t}(i_t)) \geq 2\alpha + \eta\right) \ & = \text{Pr}\left( \sum_{t=1}^T (S_{t}(i^) - \hat{S}_{t}(i^*)

• \hat{S}{t}(i^*) - \hat{S}{t}(i_t)
• \hat{S}{t}(i^*) - S{t}(i_t)) \geq 2\alpha + \eta\right) \ & \leq \text{Pr}\left( \sum_{t=1}^T (S_{t}(i^) - \hat{S}_{t}(i^)) \geq \alpha \vee \sum_{t=1}^T(\hat{S}{t}(i^*) - \hat{S}{t}(i_t)) \geq \eta \vee \sum_{t=1}^T (\hat{S}{t}(i_t) - S{t}(i_t)) \geq \alpha\right) \ & \leq \text{Pr}\left( \sum_{t=1}^T (S_{t}(i^) - \hat{S}_{t}(i^)) \geq \alpha\right)
• \text{Pr}\left(\sum_{t=1}^T(\hat{S}{t}(i^*) - \hat{S}{t}(i_t)) \geq \eta\right) + \text{Pr}\left(\sum_{t=1}^T (\hat{S}{t}(i_t) - S{t}(i_t)) \geq \alpha\right) \ & \leq \exp\left(\frac{-\gamma^2\alpha^2}{2z^2T}\right) + 0 + \exp\left(\frac{-\gamma^2\alpha^2}{2z^2T}\right) \qquad \qquad \text{(Lemmas 3, 4 and Exp3 bound)}\ & \leq 2\exp\left(\frac{-\gamma^2\alpha^2}{2z^2T}\right) \end{aligned} $$ ◻

In order to prove a bound on exploration steps in Theorem 1, we must first prove that the sum of sampling probabilities is not too high.

A bound on sampling probabilities

Lemma 6.

If a learner selects arms $i_1,...i_T$ and sampling probabilities $b_{1,i_1},...,b_{T,i_T}$ as described in Theorem 1, and furthermore, $$\sum _{t=1}^T\left(S_t\right(i^{\ast })-S_t(i_t\left)\right)\le 2\alpha +\eta )$$

where $\eta =2\frac{(z+1)}{\gamma }\sqrt{(e-1)K\ln \left(K\right)T}$ and $\alpha >0$, then, the sum of the sampling probabilities used is bounded by:

$$\sum _{t=1}^T{b}_{t,i_t}\le \frac{H}{z}(2\alpha +\eta +T)$$

Proof of Lemma 6.

First note that a best arm $i^{\ast }$ must have non-negative total score on the surrogate problem:

$$\begin{array}{ccccc}\exists i^{\prime }\in I\text{s.t.}\forall t{C}_t\left(i^{\prime }\right)=0& & & & \\ \exists i^{\prime }\in I\text{s.t.}\forall t{M}_t\left(i^{\prime }\right)\ge 0& & & & \left(R_t\right(i^{\prime })\ge 0)\\ \therefore \sum _{t=1}^{T}M\left(i^{\ast }\right)\ge 0& & & & \\ \therefore \sum _{t=1}^{T}S\left(i^{\ast }\right)\ge 0& & & & \left(S_t\right(i)\ge M_t(i\left)\right)\end{array}$$

If ${\sum }_{t=1}^T\left(S_t\right(i^{\ast })-S_t(i_t\left)\right)\le 2\alpha +\eta$, then: $$\begin{array}{cc}\sum _{t=1}^T(-S_t(i_t\left)\right)& \le 2\alpha +\eta \\ \sum _{t=1}^T(-R_t(i_t)+z{a}_{t,i_t})& \le \\ -T+\sum _{t=1}^{T}z{a}_{t,i_t}& \le \\ \therefore \sum _{t=1}^T{a}_{t,i_t}& \le \frac{1}{z}(2\alpha +\eta +T)\\ \sum _{t=1}^T\frac{{\hat{a}}_{t,i_t}}{H}& \le \\ \therefore \sum _{t=1}^T{b}_{t,i_t}& \le \frac{H}{z}(2\alpha +\eta +T)\end{array}$$

where $\eta =2\frac{(z+1)}{\gamma }\sqrt{(e-1)K\ln \left(K\right)T}$, and $\alpha >0$.

◻

\section{Bounding the overall regret}

Lemma 7.

If a learner selects arms $i_1,...i_T$ and sampling probabilities $b_{1,i_1},...,b_{T,i_T}$ as described in Theorem 1, and furthermore, $$\sum _{t=1}^T\left(S_t\right(i^{\ast })-S_t(i_t\left)\right)\le 2\alpha +\eta )$$

where $\eta =2\frac{(z+1)}{\gamma }\sqrt{(e-1)K\ln \left(K\right)T}$, and $\alpha >0$, then regret will be bounded as:

$$\sum _{t=1}^T\left(M_t\right(i^{\ast })-(1-b_{t,i_t}\left)M_t\right(i_t\left)\right)\le 2\alpha +\eta +\frac{H}{z}(2\alpha +\eta +T)$$

Proof of Lemma 7

If ${\sum }_{t=1}^T\left(S_t\right(i^{\ast })-S_t(i_t\left)\right)\le 2\alpha +\eta$ where $\eta =2\frac{(z+1)}{\gamma }\sqrt{(e-1)K\ln \left(K\right)T}$, and $\alpha >0$, then Lemma 6 gives us that: $$\begin{array}{cc}\sum _{t=1}^T{b}_{t,i_t}& \le \frac{H}{z}(2\alpha +\eta +T)\\ \therefore \sum _{t=1}^T{b}_{t,i_t}{S}_t{i}_t& \le \frac{H}{z}(2\alpha +\eta +T)\\ \therefore \sum _{t=1}^T\left(S_t\right(i^{\ast })-S_t(i_t\left)\right)+\sum _{t=1}^T{b}_{t,i_t}{S}_t{i}_t& \le 2\alpha +\eta +\frac{H}{z}(2\alpha +\eta +T)\\ \sum _{t=1}^T\left(S_t\right(i^{\ast })-(1-b_{t,i_t}\left)S_t\right(i_t\left)\right)& \le \end{array}$$

Using Lemma 2, we know that this bound on regret will give the learner a good net payoff: $$\sum _{t=1}^T\left(M_t\right(i^{\ast })-(1-b_{t,i_t}\left)M_t\right(i_t\left)\right)\le 2\alpha +\eta +\frac{H}{z}(2\alpha +\eta +T)$$

◻

Completing the proof of Theorem 1

Proof of Theorem 1 For the learner to succeed, two things must happen. First, its sampling error must not cause too much regret. Second, it must not have too many exploration steps:

$$\begin{array}{cc}& \text{Pr}(\sum _{t=1}^T{F}_t\ge \zeta +\frac{H}{z}(2\alpha +\eta +T)\vee \sum _{t=1}^T(M_t\left(i^{\ast }\right)-(1-b_{t,i_t})M_t\left(i_t\right)\ge 2\alpha +\eta +\frac{2\alpha +\eta +T}{z})\\ & \le \text{Pr}\left(\sum _{t=1}^T\right(F_t-b_{t,i_t})\ge \zeta \vee \sum _{t=1}^T{b}_{t,i_t}\ge \frac{H}{z}(2\alpha +\eta +T)\vee \sum _{t=1}^T(S_t\left(i^{\ast }\right)-S_t\left(i_t\right)\ge 2\alpha +\eta )\\ & \le \text{Pr}\left(\sum _{t=1}^T\right(F_t-b_{t,i_t})\ge \zeta \vee \sum _{t=1}^T(S_t\left(i^{\ast }\right)-S_t\left(i_t\right)\ge 2\alpha +\eta )\left(\text{Lemma 6}\right)\\ & \le \text{Pr}\left(\sum _{t=1}^T\right(F_t-b_{t,i_t})\ge \zeta )+\text{Pr}\left(\sum _{t=1}^T\right(S_t\left(i^{\ast }\right)-S_t\left(i_t\right)\ge 2\alpha +\eta )\left(\text{Union bound}\right)\end{array}$$ From Lemma 5, we can bound the surrogate performance as: $\text{Pr}\left({\sum }_{t=1}^T\right(S_t\left(i^{\ast }\right)-S_t\left(i_t\right)\ge 2\alpha +\eta )\le 2\exp \left(\frac{-{\gamma }^2{\alpha }^2}{2z^{2}T}\right)$. Using Azuma's inequality, we can also bound $\text{Pr}\left({\sum }_{t=1}^T\right(F_t-b_{t,i_t})\ge \zeta )$, in order to complete the result. Since $F_t$ is an unbiased estimate of $b_{t,i_t}$, we have the Martingale:

$$Z_t=\sum _{t^{\prime }=1}^t(F_{t^{\prime }}-b_{t^{\prime }})$$ where $|Z_t-Z_{t-1}|<2$.

By Azuma's inequality, we have $\text{Pr}\left({\sum }_{t=1}^T\right(F_t-b_{t,i_t})\ge \zeta )\le \exp \left(\frac{-{\zeta }^2}{8T}\right)$, where $\zeta >0$. So we obtain:

$$\begin{array}{cc}& \text{Pr}(\sum _{t=1}^T{F}_t\ge \zeta +\frac{H}{z}(2\alpha +\eta +T)\vee \sum _{t=1}^T(M_t\left(i^{\ast }\right)-(1-b_{t,i_t})M_t\left(i_t\right))\ge 2\alpha +\eta +\frac{2\alpha +\eta +T}{z})\\ & \le 2\exp \left(\frac{-{\gamma }^2{\alpha }^2}{2z^{2}T}\right)+\exp \left(\frac{-{\zeta }^2}{8T}\right)\end{array}$$

◻

Achieving sublinear regret and sublinear exploration

What remains is to appropriately set the learner's parameters to achieve sublinear exploration and regret. If we set the parameters to $\gamma =T^{\frac{-1}{6}}$, $z=T^{\frac{1}{6}}$, and the constants to $\alpha =\sqrt{-2\log \left(\delta /3\right)}{T}^{\frac{5}{6}}$ and $\zeta =2\sqrt{-2\log \left(\delta /3\right)T}$, we have $\eta =2\nu (T^{\frac{1}{6}}+1)T^{\frac{2}{3}}$, and this yields an algorithm that will with $(1-\delta )$ probability achieve an error of less than $ϵ$ where:

$$\begin{array}{cc}ϵ=2\sqrt{-2\log \left(\delta /3\right)}{T}^{\frac{5}{6}}+2\nu (T^{\frac{1}{6}}+1)T^{\frac{2}{3}}+\frac{1}{T^{\frac{1}{6}}}(2\sqrt{-2\log \left(\delta /3\right)}{T}^{\frac{5}{6}}+2\nu (T^{\frac{1}{6}}+1)T^{\frac{2}{3}}+T)& \\ & =(2\sqrt{-2\log \left(\delta /3\right)}+2\nu +1)T^{\frac{5}{6}}+O\left(T^{\frac{2}{3}}\right)\\ & =O\left(\right(\sqrt{\log \left(\delta \right)}+\sqrt{K\ln \left(K\right)}\left)T^{\frac{5}{6}}\right)\end{array}$$

and the number of exploration steps is: $$\begin{array}{cc}\sum _{t=1}^T{F}_t& \le 2\sqrt{-2\log \left(\delta /3\right)T}+\frac{H}{T^{\frac{1}{6}}}(2\sqrt{-2\log \left(\delta /3\right)}{T}^{\frac{5}{6}}+2\nu (T^{\frac{1}{6}}+1)T^{\frac{2}{3}}+T)\\ & =O\left(\sqrt{K\ln \left(K\right)}{T}^{\frac{5}{6}}\right)\end{array}$$ That is to say that the regret and number of exploration steps will both be of order $O\left(T^{\frac{5}{6}}\right)$ with probability $1-\delta$, and do not depend on the risk-tolerance, $\tau$.

Discussion

The main aim of this post has been to develop a new model where a bandit algorithm can learn to avoid catastrophes. We have seen that a learner can avoid catastrophes by a process that includes switching between exploration and deployment steps. The modelling assumptions were that it can access overestimates ${\hat{a}}_{t,i_t}$ of the ideal rate at which to sample for a catastrophe, such that these estimates are not overall too sensitive to nonserious catastrophic risks: ${\sum }_{t=1}^T{\hat{a}}_{t,i_t}\le H{\sum }_{t=1}^T{a}_{t,i_t}$, and that there is some arm that carries no catastrophic risk.

These assumptions could have some difficulties in practice. Many AI systems can avoid causing catastrophes be remaining immobile or inert, but others such as self-driving cars and spy drones, do not have this luxury. Obtaining the estimates of catastrophe risk would also be very difficult. In general, a lot of data would be required, which might perhaps have to be labelled using simulations and/or by human operators. There is further work to be done in trying to relax some of these assumptions.

Since this is just a proof of concept, the regret and exploration bounds are both of order $T^{\frac{5}{6}}$, and we have left this bound very loose. Ultimately, the aim would be to achieve efficiency nearer to the order of $T^{\frac{2}{3}}$ in keeping with a similar class of games lacking "local observability" as described by Bartok et al [2]. We have some ideas about how to achieve this, and will post our results.

References

1. The bound on Exp3 is given in the discussion of Corrollary 4.2 on page 8-9 in Auer, Peter, et al. "Gambling in a rigged casino: The adversarial multi-armed bandit problem." Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on. IEEE, 1995.
2. See Bartók, Gábor, et al. "Partial monitoring-classification, regret bounds, and algorithms." Mathematics of Operations Research 39.4 (2014): 967-997.

0 comments

Comments sorted by top scores.