Are bandits considered an RL approach?

Question

If a research paper uses multi-armed bandits (either in their standard or contextual form) to solve a particular task, can we say that they solved this task using a reinforcement learning approach? Or should we distinguish between the two and use the RL term only when it is associated with an MDP formulation?

In fact, each RL course/textbook usually contains a section about bandits (especially when dealing with the exploration-exploitation tradeoff). Additionally, bandits also have the concept of actions and rewards.

I just want to make sure what the right terminology should be, when describing either approach.

Answer 1

Several important researchers distinguish between bandit problems and the general reinforcement learning problem.

The book Reinforcement learning: an introduction by Sutton and Barto describes bandit problems as a special case of the general RL problem.

The first chapter of this part of the book describes solution methods for the special case of the reinforcement learning problem in which there is only a single state, called bandit problems. The second chapter describes the general problem formulation that we treat throughout the rest of the book — finite Markov decision processes — and its main ideas including Bellman equations and value functions.

This means that you can represent your bandit problem as an MDP with a single state and possibly multiple actions.

In section 1.1.2 of the book Bandit Algorithms (2020), Szepesvari and Lattimore describe the differences between bandits and reinforcement learning

One of the distinguishing features of all bandit problems studied in this book is that the learner never needs to plan for the future. More precisely, we will invariably make the assumption that the learner's available choices and rewards tomorrow are not affected by their decisions today. Problems that do require this kind of long-term planning fall into the realm of reinforcement learning

This definition is different than the one by Sutton and Barto. In this case, only bandit problems where the learner doesn't need to plan for the future are considered.

In any case, bandit problems and RL problems have a lot of similarities. For example, both attempt to deal with the exploration-exploitation trade-off and, in both cases, the underlying problem can be formulated as a Markov decision process.

Answer 2

Let's have a look at the introduction of Chapter 2: Multi-armed Bandits in the Reinforcement Learning: An Introduction by Sutton, Barto

The most important feature distinguishing reinforcement learning from other types of learning is that it uses training information that evaluates the actions taken rather than instructs by giving correct actions. This is what creates the need for active exploration, for an explicit search for good behavior. Purely evaluative feedback indicates how good the action taken was, but not whether it was the best or the worst action possible. Purely instructive feedback, on the other hand, indicates the correct action to take, independently of the action actually taken. This kind of feedback is the basis of supervised learning, which includes large parts of pattern classification, artificial neural networks, and system identification. In their pure forms, these two kinds of feedback are quite distinct: evaluative feedback depends entirely on the action taken, whereas instructive feedback is independent of the action taken. In this chapter we study the evaluative aspect of reinforcement learning in a simplified setting, one that does not involve learning to act in more than one situation. This nonassociative setting is the one in which most prior work involving evaluative feedback has been done, and it avoids much of the complexity of the full reinforcement learning problem. Studying this case enables us to see most clearly how evaluative feedback differs from, and yet can be combined with, instructive feedback. The particular nonassociative, evaluative feedback problem that we explore is a simple version of the k-armed bandit problem. We use this problem to introduce a number of basic learning methods which we extend in later chapters to apply to the full reinforcement learning problem. At the end of this chapter, we take a step closer to the full reinforcement learning problem by discussing what happens when the bandit problem becomes associative, that is, when actions are taken in more than one situation.

Since bandits involve evaluative feedback they are indeed a type of a (simplified) reinforcement learning problem.