Guest post by Mark Sellke.
In the comments of the previous blog post we asked if the new viewpoint on best of both worlds can be used to get clean “interpolation” results. The context is as follows: in a STOC 2018 paper followed by a COLT 2019 paper, the following corruption model was discussed: stochastic bandits, except for rounds which are adversarial. The state of the art bounds were of the form: optimal (or almost optimal) stochastic term plus
, and it was mentioned as an open problem whether
could be improved to
(there is a lower bound showing that
is necessary — when
). As was discussed in the comment section, it seemed that indeed this clean best of both worlds approach should certainly shed light on the corruption model. It turns out that this is indeed the case, and a one-line calculation resolves positively the open problem from the COLT paper. The formal result is as follows (recall the notation/definitions from the previous blog post):
Lemma: Consider a strategy whose regret with respect to the optimal action
is upper bounded by
(1)
Then in the
-corruption stochastic bandit model one has that the regret is bounded by:
Note that by the previous blog post we know strategies that satisfy (1) with (see Lemma 2 in the previous post).
Proof: In equation (1) let us apply Jensen over the corrupt rounds, this yields a term . For the non-corrupt rounds, let us use that
The sum of the second term on the right hand side is upper bounded by . On the other hand the sum (over non-corrupt rounds) of the first term is equal to
of the regret over the non-corrupt rounds, which is certainly smaller than
of the total regret plus
. Thus we obtain (denoting
for the total regret):
which concludes the proof.
By flowersandfashion.online February 15, 2021 - 6:23 am
https://flowersandfashion.online
By fastmortgage.club February 15, 2021 - 6:22 am
https://fastmortgage.club
By traveltricks.club February 15, 2021 - 6:22 am
https://traveltricks.club
By yourinjuryattorneys.club February 15, 2021 - 6:21 am
https://yourinjuryattorneys.club
By realestatehouselistings.club February 15, 2021 - 6:20 am
https://realestatehouselistings.club
By poker-casino.club February 15, 2021 - 6:20 am
https://poker-casino.club
By etnews.club February 15, 2021 - 6:19 am
https://etnews.club
By fitness-story.club February 15, 2021 - 6:19 am
https://fitness-story.club
By crossfirecoins.club February 15, 2021 - 6:17 am
https://crossfirecoins.club
By eusedcarloans.club February 15, 2021 - 6:16 am
https://eusedcarloans.club
By travelguider.club February 15, 2021 - 6:16 am
https://travelguider.club
By yourattorney.club February 15, 2021 - 6:15 am
https://yourattorney.club
By realestateglobal.club February 15, 2021 - 6:15 am
https://realestateglobal.club
By onlinecasinoroyal.club February 15, 2021 - 6:14 am
https://onlinecasinoroyal.club
By jannie.club February 15, 2021 - 6:13 am
https://jannie.club
By fashionxtreme.club February 15, 2021 - 6:13 am
https://fashionxtreme.club
By etransferloan.club February 15, 2021 - 6:12 am
https://etransferloan.club
By travelersonline.club February 15, 2021 - 6:11 am
https://travelersonline.club
By usattorneys.club February 15, 2021 - 6:11 am
https://usattorneys.club
By realestateblog.club February 15, 2021 - 6:10 am
https://realestateblog.club
By modern-coin.club February 15, 2021 - 6:10 am
https://modern-coin.club
By 365flix.online February 15, 2021 - 6:09 am
https://365flix.online
By zigmawb.online February 15, 2021 - 6:08 am
https://zigmawb.online
By thomasine.club February 15, 2021 - 6:07 am
https://thomasine.club