How do I recognise a bandit problem?

Question

I'm having difficulty understanding the distinction between a bandit problem and a non-bandit problem.

An example of the bandit problem is an agent playing $n$ slot machines with the goal of discovering which slot machine is the most probable to return a reward. The agent learns to find the best strategy of playing and is allowed to pull the lever of one slot machine per time step. Each slot machine obeys a distinct probability of winning.

In my interpretation of this problem, there is no notion of state. The agent potentially can utilise the slot results to determine a state-action value? For example, if a slot machine pays when three apples are displayed, this is a higher state value than a state value where three apples are not displayed.

Why is there just one state in the formulation of this bandit problem? As there is only one action ("pulling the slot machine lever" ), then there is one action. The slot machine action is to pull the lever, which starts the game.

I am taking this a step further now. An RL agent purchases $n$ shares of an asset and its not observable if the purchase will influence the price. The next state is the price of the asset after the purchase of the shares. If $n$ is sufficiently large, then the price will be affected otherwise there is a minuscule if any effect on the share price. Depending on the number of shares purchased at each time step, it's either a bandit problem or not.

It is not a bandit problem if $n$ is large and the share price is affected? It is a bandit problem if $n$ is small and the share price is not affected?

Does it make sense to have a mix of a bandit and non-bandit states for a given RL problem? If so, then the approach to solving should be to consider the issue in its entirety as not being a bandit problem?

Answer 1

The bandit problem has one state, in which you are allowed to choose one lever among $n$ levers to pull.

Why is there just one state in the formulation of this bandit problem?

There is one state because the state does not change over time. Two notable consequences are that (i) pulling a lever does not change the internals of any slot machine (e.g. the distribution of rewards) and (ii) you are allowed to choose any lever without restrictions. More generally, there is no sequential aspect of the state in this problem, as future states are unaffected by past states, actions, and rewards.

It is not a bandit problem if $n$ is large and the share price is affected?

Correct! If the share price is affected, then future states would be influenced by past actions. This is because the price per share is affected, which is one aspect of the state. Thus, you would need to plan a sequential strategy for your purchases.

It is a bandit problem if $n$ is small and the share price is not affected?

It all depends on the problem: as long as the state before buying shares remains completely the same after you purchase some shares, then yes. Share price being unaffected is only one of the requirements; another example requirement is that the maximum number of shares purchased is fixed at each time step, independent of the shares purchased previously.

Does it make sense to have a mix of a bandit and non-bandit states for a given RL problem? If so, then the approach to solving should be to consider the issue in its entirety as not being a bandit problem?

It makes sense to allow the share price to either be affected or unaffected based on $n$ in the same problem. Since some actions (large $n$) change the state, then there are multiple states, and actions sequentially affect the next state. Hence it is not a bandit problem as a whole, as you correctly stated.

The agent potentially can utilise the slot results to determine a state-action value?

Correct! I suggest reading Chapter 2 of Sutton and Barto to learn some fundamental algorithms of developing such strategies.

Nice work on analyzing this problem! To help solidify your understanding and formalize the arguments above, I suggest that you rewrite the variants of this problem as MDPs and determine which variants have multiple states (non-bandit) and which variants have a single state (bandit).