Episodic Multi-armed Bandits

We introduce a new class of reinforcement learning methods referred to as em episodic multi-armed bandits (eMAB). In eMAB the learner proceeds in em episodes, each composed of several em steps, in which it chooses an action and observes a feedback signal. Moreover, in each step, it can take a special action, called the stop action, that ends the current episode. After the stop action is taken, the learner collects a terminal reward, and observes the costs and terminal rewards associated with each step of the episode. The goal of the learner is to maximize its cumulative gain (i.e., the terminal reward minus costs) over all episodes by learning to choose the best sequence of actions based on the feedback. First, we define an em oracle benchmark, which sequentially selects the actions that maximize the expected immediate gain. Then, we propose our online learning algorithm, named em FeedBack Adaptive Learning (FeedBAL), and prove that its regret with respect to the benchmark is bounded with high probability and increases logarithmically in expectation. Moreover, the regret only has polynomial dependence on the number of steps, actions and states. eMAB can be used to model applications that involve humans in the loop, ranging from personalized medical screening to personalized web-based education, where sequences of actions are taken in each episode, and optimal behavior requires adapting the chosen actions based on the feedback.