Reinforcement Learning Algorithms with Python

Exploration complexity

We saw how UCB, and in particular UCB1, can reduce the overall regret and accomplish an optimal convergence on the multi-armed bandit problem with a relatively easy algorithm. However, this is a simple stateless task.

So, how will UCB perform on more complex tasks? To answer this question, we can oversimplify the division and group all of the problems in these three main categories:

• Stateless problems: An instance of these problems is the multi-armed bandit. The exploration in such cases can be handled with a more sophisticated algorithm, such as UCB1.
• Small-to-medium tabular problems: As a basic rule, exploration can still be approached with more advanced mechanisms, but in some cases, the overall benefit is small, ...