Episodic Bandits with Stochastic Experts
We study a version of the contextual bandit problem where an agent can intervene through a set of stochastic expert policies. The agent interacts with the environment over episodes, with each episode having different context distributions; this results in the `best expert' changing across episodes. Our goal is to develop an agent that tracks the best expert over episodes. We introduce the Empirical Divergence-based UCB (ED-UCB) algorithm in this setting where the agent does not have any knowledge of the expert policies or changes in context distributions. With mild assumptions, we show that bootstrapping from $\mathcal{O}(N\log(NT^2\sqrt{E}))$ samples results in a regret of $\mathcal{O}(E(N+1) + \frac{N\sqrt{E}}{T^2})$ for $N$ experts over $E$ episodes, each of length $T$. If the expert policies are known to the agent a priori, then we can improve the regret to $\mathcal{O}(EN)$ without requiring any bootstrapping. Our analysis also tightens pre-existing logarithmic regret bounds to a problem-dependent constant in the non-episodic setting when expert policies are known. We finally empirically validate our findings through simulations.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Contextual Bandits with Stochastic Experts
We consider the problem of contextual bandits with stochastic experts, which is a variation of the traditional stochastic contextual bandit with experts problem. In our problem setting, we assume access to a class of sto…
Multi-Armed BanditsBeen There, Done That: Meta-Learning with Episodic Recall
Meta-learning agents excel at rapidly learning new tasks from open-ended task distributions; yet, they forget what they learn about each task as soon as the next begins. When tasks reoccur - as they do in natural environ…
Meta-LearningNonstochastic Bandits with Infinitely Many Experts
We study the problem of nonstochastic bandits with expert advice, extending the setting from finitely many experts to any countably infinite set: A learner aims to maximize the total reward by taking actions sequentially…
BenchmarkingMeta-LearningSimultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition
This work studies the problem of learning episodic Markov Decision Processes with known transition and bandit feedback. We develop the first algorithm with a ``best-of-both-worlds'' guarantee: it achieves $\mathcal{O}(lo…
Multi-Armed BanditsNonstochastic Bandits and Experts with Arm-Dependent Delays
We study nonstochastic bandits and experts in a delayed setting where delays depend on both time and arms. While the setting in which delays only depend on time has been extensively studied, the arm-dependent delay setti…