Confusion in the "goal" of multi arm bandit problem

Question

Say, we have $n$ actions to choose from, assume that after an action has been chosen, the state of the system stays the same, only our knowledge gets updated. What exactly is the goal of the multi arm bandit problem?

1. Is it that we want to find the action that has highest expected mean reward, so that after sufficiently long amount of time, we have gotten one ideal action? Here it seems that one should always go for exploration, for each state perform the experiment very high number of times, to get an accurate estimate of the expected reward and then we are guaranteed to find the best action to always go for in the future.

2. Is it that I want to maximize the total reward accumulated over time due to repetition of the experiment? Here, I will have to be careful about my strategy and hence I need to ponder over exploitation vs exploration.

Background

I am reading chapter 2 of Sutton's Reinforcement learning. But it seems very verbose, confusing and convoluted. Please provide any general suggestions that you might have, should I stick to the book or try something else? I think I might be too much used to definition, theorem, proof style of presentation.

Answer 1

The specific goal for an instance of a bandit problem will depend on why you want to use the framework. S&B is being cicumspect about it, because they are offering more broad analysis.

In practice, you would often use the bandit approach on "live" systems where you are not able to simulate or have pre-existing data for the choices being made. It is a common approach in web advertising to optimise click-through of adverts that have not been seen before.

In that scenario, you care about the explore/exploit trade-off and maximising returns whilst learning (there is often a financial impact to optimise here). This is often phrased as minimising regret which is usually measured as total of expected return from actions taken compared to selecting the (in hindsight) best action on every attempt.

S&B don't go into bandit problems in any depth. In that book, bandit problems are being used to illustrate the explore vs exploit tradeoff for learning from experience, in isolation, before then diving into the full reinforcement learning problem.

Out of the options in your question:

2. Is it that I want to maximize the total reward accumulated over time due to repetition of the experiment?

This is the more common use case and goal for applying bandit problem theory. The theory is slightly broader than that, as it attempts to model a group of problems, and you can explore aspects of these models and associated algorithms.