Today, due to the increase in available products and services, it is becoming increasingly difficult for a user to find what they are looking for. For this reason, having a good recommendation system is crucial for the success of an e-commerce platform.
Recommendation systems are tools that are widely used today. We see them on streaming platforms, travel applications, diet apps, and even banking products use them to improve the user experience by providing personalized and relevant recommendations.
A powerful but not very well-known tool for building these systems is Multi-Armed Bandits, a family of algorithms that belong to the field of reinforcement learning and enable real-time decision-making in uncertain environments.
In this article, we will explore the world of bandits and their applications to recommendation systems, highlighting the benefits and limitations of this approach.
Basic concepts of Reinforcement Learning
Reinforcement Learning (RL) is an area of Machine Learning that differs from supervised or unsupervised learning. Unlike those approaches, reinforcement learning models learn through experience, using reward or punishment feedback with the goal of maximizing cumulative reward.
The key concepts of Reinforcement Learning can be summarized as follows:
- Agent: the entity that makes decisions.
- Policy: the strategy that defines how the agent makes decisions.
- Action: the decision the agent takes at a given moment.
- Environment: the context in which the agent acts and receives rewards.
- State: the current description of the environment at a given moment.
- Reward: the measure of success.
Another important concept in reinforcement learning is that of a stateless algorithm, meaning one that does not make decisions based on the previous state of the environment. This type of algorithm only makes decisions based on previously obtained rewards and, optionally, the current state. The Multi-Armed Bandit (MAB) we will see below is a stateless algorithm.
What is the Multi-Armed Bandit problem?
The Multi-Armed Bandit problem is a classic stateless problem in reinforcement learning. It is presented as a hypothetical experiment in which a player is given a slot machine with several arms and knows that some will give more rewards than others, but does not know which ones. Their goal is to pull the arms to obtain the highest possible reward by the end of the game. The question is: What is the best strategy to achieve the highest long-term benefit?
Should they exploit their current knowledge to maximize immediate reward, or should they explore new options to gather valuable information that might improve long-term performance?
This situation is known as the exploration/exploitation dilemma, which appears frequently in reinforcement learning, but also in everyday life. Should we try a new restaurant at the risk of not liking it, or go back to the one we already know is good?
One of the key aspects of Multi-Armed Bandit algorithms is that they balance exploration and exploitation: testing new recommendations (explore) and selecting those with the highest probability of success (exploit).
The formal formulation of the problem can be summarized, broadly speaking, with the following scheme. For each time t, we have:
Business applications of MAB
Some current applications of MAB include:
- Headline selection: News has a very short lifespan and bandit algorithms can determine the best headline or CTA much faster than a classic A/B test.
- Short campaigns and promotions: Similarly, for a short campaign (one week, one month…), there is no time to spend half the period exploring, since once the best option is learned, it may be too late to exploit it.
- Medical treatment optimisation: Bandits help maximise treatment effectiveness by gradually choosing the most effective option based on real-time feedback.
In recommendation systems, the business relevance is clear. When offering products to a user, we are not merely interested in predicting whether they will click, but instead in showing the product they are most likely to click maximizing cumulative reward. Thanks to the exploration/exploitation balance, using a MAB in a recommendation system allows us to explore different options to better understand user preferences, while exploiting what we already know will work.
Key MAB policies
How does the agent select the best option? In the literature, many algorithms aim to achieve this goal: some use contextual variables, some do not; some take a deterministic approach, others a Bayesian one, etc.
Without going into mathematical detail, some of the most commonly used policies are:
- ε-greedy: With probability ε, the algorithm chooses a random recommendation to explore; with probability 1−ε, it chooses the recommendation with the highest observed success rate.
- UCB1: Improves on ε-greedy by also incorporating uncertainty, considering both the observed reward and how much is known about each arm.
- Bernoulli Thompson Sampling: A Bayesian approach used when rewards are binary. It models uncertainty with probability distributions (Beta distributions) and updates them after each iteration.
- LinUCB: Based on UCB1 but incorporates contextual variables, assuming the reward depends linearly on them.
- LinTS: The Bayesian counterpart to LinUCB, using Thompson Sampling with contextual variables and linear models.
Conclusion
Multi-Armed Bandit problems offer an interesting way to explore reinforcement learning and are a strong alternative for developing recommendation systems in situations where labeled data is very limited or does not exist at all.
One of their greatest advantages is the ability to optimize the user experience incrementally and in real time, with added personalization based on current user information. This makes them highly valuable when decisions must be made instantly, without waiting to collect a large amount of labeled data.
However, there are also drawbacks. Many policies and implementations exist, and evaluating them using data generated by a different policy is not trivial. Moreover, choosing the best policy depends heavily on the specific dataset, meaning that an implementation might not be transferable to another business case.
If you want to learn more about these algorithms, recommendation systems, predictive models or Linkroad, contact us.