paper-with-me

홈 › Papers

Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays

2021-10-26 · Jiatai Huang, Yan Dai, Longbo Huang

We consider the Scale-Free Adversarial Multi-Armed Bandit (MAB) problem with unrestricted feedback delays. In contrast to the standard assumption that all losses are $[0,1]$-bounded, in our setting, losses can fall in a general bounded interval $[-L, L]$, unknown to the agent beforehand. Furthermore, the feedback of each arm pull can experience arbitrary delays. We propose a novel approach named Scale-Free Delayed INF (SFD-INF) for this novel setting, which combines a recent "convex combination trick" together with a novel doubling and skipping technique. We then present two instances of SFD-INF, each with carefully designed delay-adapted learning scales. The first one SFD-TINF uses $\frac 12$-Tsallis entropy regularizer and can achieve $\widetilde{\mathcal O}(\sqrt{K(D+T)}L)$ regret when the losses are non-negative, where $K$ is the number of actions, $T$ is the number of steps, and $D$ is the total feedback delay. This bound nearly matches the $\Omega((\sqrt{KT}+\sqrt{D\log K})L)$ lower-bound when regarding $K$ as a constant independent of $T$. The second one, SFD-LBINF, works for general scale-free losses and achieves a small-loss style adaptive regret bound $\widetilde{\mathcal O}(\sqrt{K\mathbb{E}[\tilde{\mathfrak L}_T^2]}+\sqrt{KDL})$, which falls to the $\widetilde{\mathcal O}(\sqrt{K(D+T)}L)$ regret in the worst case and is thus more general than SFD-TINF despite a more complicated analysis and several extra logarithmic dependencies. Moreover, both instances also outperform the existing algorithms for non-delayed (i.e., $D=0$) scale-free adversarial MAB problems, which can be of independent interest.

📄 PDF Abstract BibTeX arXiv:2110.13400

Code (0)

등록된 구현이 없습니다.

Similar Papers 제목 키워드 기반

Scale-free Adversarial Reinforcement Learning

2024-03-01 · Mingyu Chen, Xuezhou Zhang

This paper initiates the study of scale-free learning in Markov Decision Processes (MDPs), where the scale of rewards/losses is unknown to the learner. We design a generic algorithmic framework, \underline{S}cale \underl…

reinforcement-learningReinforcement Learning

Scale Free Adversarial Multi Armed Bandits

2021-06-08 · Sudeep Raja Putta, Shipra Agrawal

We consider the Scale-Free Adversarial Multi Armed Bandits(MAB) problem. At the beginning of the game, the player only knows the number of arms $n$. It does not know the scale and magnitude of the losses chosen by the ad…

Multi-Armed Bandits

Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learning

2023-01-25 · Jiatai Huang, Yan Dai, Longbo Huang

We propose Banker Online Mirror Descent (Banker-OMD), a novel framework generalizing the classical Online Mirror Descent (OMD) technique in the online learning literature. The Banker-OMD framework almost completely decou…

Multi-Armed Bandits

Pareto Regret Analyses in Multi-objective Multi-armed Bandit

2022-12-01 · Mengfan Xu, Diego Klabjan

We study Pareto optimality in multi-objective multi-armed bandit by providing a formulation of adversarial multi-objective multi-armed bandit and defining its Pareto regrets that can be applied to both stochastic and adv…

Adversarial Attack

Bridging Adversarial and Nonstationary Multi-armed Bandit

2022-01-05 · Ningyuan Chen, Shuoguang Yang, Hailun Zhang

In the multi-armed bandit framework, there are two formulations that are commonly employed to handle time-varying reward distributions: adversarial bandit and nonstationary bandit. Although their oracles, algorithms, and…