Home Artificial Intelligence Dynamic Pricing with Multi-Armed Bandit: Learning by Doing Dynamic Pricing, Reinforcement Learning and Multi-Armed Bandit Modeling The Demand Curve Multi-armed Bandit Strategies How will we evaluate the outcomes? Running the simulation Results Lessons learned and next steps References

Dynamic Pricing with Multi-Armed Bandit: Learning by Doing Dynamic Pricing, Reinforcement Learning and Multi-Armed Bandit Modeling The Demand Curve Multi-armed Bandit Strategies How will we evaluate the outcomes? Running the simulation Results Lessons learned and next steps References

0
Dynamic Pricing with Multi-Armed Bandit: Learning by Doing
Dynamic Pricing, Reinforcement Learning and Multi-Armed Bandit
Modeling The Demand Curve
Multi-armed Bandit Strategies
How will we evaluate the outcomes?
Running the simulation
Results
Lessons learned and next steps
References

Applying Reinforcement Learning strategies to real-world use cases, especially in dynamic pricing, can reveal many surprises

Towards Data Science
Photo by Markus Spiske on Unsplash

Within the vast world of decision-making problems, one dilemma is especially owned by Reinforcement Learning strategies: exploration versus exploitation. Imagine walking right into a casino with rows of slot machines (also often called “one-armed bandits”) where each machine pays out a unique, unknown reward. Do you explore and play each machine to find which one has the very best payout, or do you persist with one machine, hoping it’s the jackpot? This metaphorical scenario underpins the concept of the Multi-armed Bandit (MAB) problem. The target is to search out a method that maximizes the rewards over a series of plays. While exploration offers recent insights, exploitation leverages the data you already possess.

Now, transpose this principle to dynamic pricing in a retail scenario. Suppose you might be an e-commerce store owner with a brand new product. You aren’t certain about its optimal selling price. How do you set a price that maximizes your revenue? Must you explore different prices to grasp customer willingness to pay, or must you exploit a price that has been performing well historically? Dynamic pricing is actually a MAB problem in disguise. At every time step, every candidate price point will be seen as an “arm” of a slot machine and the revenue generated from that price is its “reward.” One other approach to see that is that the target of dynamic pricing is to swiftly and accurately measure how a customer base’s demand reacts to various price points. In simpler terms, the aim is to pinpoint the demand curve that best mirrors customer behavior.

In this text, we’ll explore 4 Multi-armed Bandit algorithms to guage their efficacy against a well-defined (though not straightforward) demand curve. We’ll then dissect the first strengths and limitations of every algorithm and delve into the important thing metrics which are instrumental in gauging their performance.

Traditionally, demand curves in economics describe the connection between the value of a product and the amount of the product that buyers are willing to purchase. They often slope downwards, representing the common remark that as price rises, demand typically falls, and vice-versa. Consider popular products akin to smartphones or concert tickets. If prices are lowered, more people are likely to buy, but when prices skyrocket, even the ardent fans might think twice.

Yet in our context, we’ll model the demand curve barely in another way: we’re putting price against probability. Why? Because in dynamic pricing scenarios, especially digital goods or services, it’s often more meaningful to think when it comes to the likelihood of a sale at a given price than to take a position on exact quantities. In such environments, each pricing attempt will be seen as an exploration of the likelihood of success (or purchase), which will be easily modeled as a Bernoulli random variable with a probability p depending on a given test price.

Here’s where it gets particularly interesting: while intuitively one might think the duty of our Multi-armed Bandit algorithms is to unearth that ideal price where the probability of purchase is highest, it’s not quite so straightforward. Actually, our ultimate goal is to maximise the revenue (or the margin). This implies we’re not trying to find the value that gets probably the most people to click ‘buy’ — we’re trying to find the value that, when multiplied by its associated purchase probability, gives the very best expected return. Imagine setting a high price that fewer people buy, but each sale generates significant revenue. On the flip side, a really low price might attract more buyers, but the whole revenue might still be lower than the high price scenario. So, in our context, talking concerning the ‘demand curve’ is somewhat unconventional, as our goal curve will primarily represent the probability of purchase moderately than the demand directly.

Now, attending to the mathematics, let’s start by saying that consumer behavior, especially when coping with price sensitivity, isn’t all the time linear. A linear model might suggest that for each incremental increase in price, there’s a continuing decrement in demand. In point of fact, this relationship is usually more complex and nonlinear. One approach to model this behavior is through the use of logistic functions, which may capture this nuanced relationship more effectively. Our chosen model for the demand curve is then:

Here, a denotes the utmost achievable probability of purchase, while b modulates the sensitivity of the demand curve against price changes. The next value of b means a steeper curve, approaching more rapidly to lower purchase probabilities as the value increases.

4 examples of demand curves with different combos of parameters a and b

For any given price point, we’ll be then capable of obtain an associated purchase probability, p. We will then input p right into a Bernoulli random variable generator to simulate the response of a customer to a selected price proposal. In other words, given a price, we are able to easily emulate our reward function.

Next, we are able to multiply this function by the value with a view to get the expected revenue for a given price point:

Unsurprisingly, this function doesn’t reach its maximum in correspondence with the very best probability. Also, the value related to the utmost doesn’t rely upon the worth of the parameter a, while the utmost expected return does.

Expected revenue curves with related maxima

With some recollection from calculus, we can even derive the formula for the derivative (you’ll need to make use of a mix of each the product and the chain rule). It’s not exactly a soothing exercise, nevertheless it’s nothing too difficult. Here is the analytical expression of the derivative of the expected revenue:

This derivative allows us to search out the precise price that maximizes our expected revenue curve. In other words, through the use of this specific formula in tandem with some numerical algorithms, we are able to easily determine the value that sets it to 0. This, in turn, is the value that maximizes the expected revenue.

And this is precisely what we want, since by fixing the values of a and b, we’ll immediately know the goal price that our bandits can have to search out. Coding this in Python is a matter of a couple of lines of code:

For our use case, we’ll set a = 2 and b = 0.042, which can give us a goal price of about 30.44, related to an optimal probability of 0.436 ( → optimal average reward is 30.44*0.436=13.26). This price is clearly unknown on the whole and it is precisely the value that our Multi-armed Bandit algorithms will seek.

Now that we’ve identified our objectives, it’s time to explore various strategies for testing and analyzing their performance, strengths, and weaknesses. While several algorithms exist in MAB literature, on the subject of real-world scenarios, 4 primary strategies (together with their variations) predominantly form the backbone. On this section, we’ll provide a temporary overview of those strategies. We assume the reader has a foundational understanding of them; nevertheless, for those all in favour of a more in-depth exploration, references are provided at the top of the article. After introducing each algorithm, we’ll also present its Python implementation. Although each algorithm possesses its unique set of parameters, all of them commonly utilize one key input: the arm_avg_reward vector. This vector denotes the common reward garnered from each arm (or motion/price) as much as the present time step t. This critical input guides all of the algorithms in making informed decisions concerning the subsequent price setting.

The algorithms I’m going to use to our dynamic pricing problem are the next:

Greedy: This strategy is like all the time going back to the machine that gave you probably the most coins the primary few times you played. After trying out each machine a bit, it sticks with the one which seemed the perfect. But there could be an issue. What if that machine was just lucky initially? The Greedy strategy might miss out on higher options. On the intense side, the code implementation is absolutely easy:

It’s essential to distinguish the initial scenario (when all rewards are 0) from the regular one. Often, you’ll find only the ‘else’ part implemented, which indeed works even when all rewards are at 0. Yet, this approach can result in a bias toward the primary element. In the event you make this oversight, you may find yourself paying that bias, particularly if the optimal reward happens to be tied to the primary arm (yes, I’ve been there). The Greedy approach is often the least-performing one and we’ll primarily use it as our performance baseline.

ϵ-greedy: The ε-greedy (epsilon-greedy) algorithm is a modification to tackle the predominant drawback of the greedy approach. It introduces a probability ε (epsilon), typically a small value, to pick out a random arm, promoting exploration. With a probability 1−ε, it chooses the arm with the very best estimated reward, favoring exploitation. By balancing between random exploration and exploitation of known rewards, the ε-greedy strategy goals to attain higher long-term returns in comparison with purely greedy methods. Again, the implementation is immediate, it’s simply an extra ‘if’ on top of the Greedy code.

UCB1 (Upper Confidence Sure): The UCB1 strategy is sort of a curious explorer trying to search out the perfect restaurant in a brand new city. While there’s a favourite spot they’ve enjoyed, the allure of probably discovering an excellent higher place grows with each passing day. In our context, UCB1 combines the rewards of known price points with the uncertainty of those less explored. Mathematically, this balance is achieved through a formula: the common reward of a price point plus an “uncertainty bonus” based on how long because it was last tried. This bonus is calculated as

and represents the “growing curiosity” concerning the untried price. The hyperparameter C controls the balance between exploitation and exploration, with higher values of C encouraging more exploration of less-sampled arms. By all the time choosing the value with the very best combined value of known reward and curiosity bonus, UCB1 ensures a combination of sticking to what’s known and venturing into the unknown, aiming to uncover the optimal price point for optimum revenue. I’ll start with the by-the-book implementation of this approach, but we’ll soon see that we want to tweak it a bit.

Thompson Sampling: This Bayesian approach addresses the exploration-exploitation dilemma by probabilistically choosing arms based on their posterior reward distributions. When these rewards adhere to a Bernoulli distribution, representing binary outcomes like success/failure, Thompson Sampling (TS) employs the Beta distribution as a conjugate prior (see this table for reference). Initiating with a non-informative Beta(1,1) prior for each arm, the algorithm updates the distribution’s parameters upon observing rewards: a hit increases the alpha parameter, while a failure augments the beta. During each play, TS draws from the present Beta distribution of every arm and opts for the one with the highest sampled value. This technique allows TS to dynamically adjust based on gathered rewards, adeptly balancing between the exploration of uncertain arms and the exploitation of those known to be rewarding. In our specific scenario, although the foundational reward function follows a Bernoulli distribution (1 for a purchase order and 0 for a missed purchase), the actual reward of interest is the product of this basic reward and the present price under test. Hence, our implementation of TS will need a slight modification (which may even introduce some surprises).

The change is definitely pretty easy: to find out probably the most promising next arm, samples extracted from the posterior estimates are multiplied by their respective price points (line 3). This modification ensures decisions are anchored on the anticipated average revenue, shifting the main focus from the very best purchase probability.

At this point, having gathered all the important thing ingredients to construct a simulation comparing the performance of the 4 algorithms in our dynamic pricing context, we must ask ourselves: what exactly will we be measuring? The metrics we decide are pivotal, as they are going to guide us within the means of each comparing and improving the algorithm implementation. On this endeavor, I’m zeroing in on three key indicators:

  1. Regret: This metric measures the difference between the reward obtained by the chosen motion and the reward that will have been obtained by taking the perfect possible motion. Mathematically, regret at time t is given by: Regret(t)=Optimal Reward(t)−Actual Reward(t). Regret, when collected over time, provides insight into how much we’ve “lost” by not all the time selecting the perfect motion. It’s preferred over cumulative reward since it provides a clearer indication of the algorithm’s performance relative to the optimal scenario. Ideally, a regret value near 0 indicates proximity to optimal decision-making.
  2. Reactivity: This metric gauges the speed at which an algorithm approaches a goal average reward. Essentially, it’s a measure of the algorithm’s adaptability and learning efficiency. The quicker an algorithm can achieve the specified average reward, the more reactive it’s, implying a swifter adjustment to the optimal price point. In our case the goal reward is about at 95% of the optimal average reward, which is 13.26. Nonetheless, initial steps can exhibit high variability. For example, a lucky early selection might end in a hit from a low probability arm related to a high price, quickly achieving the brink. Attributable to such fluctuations, I’ve opted for a stricter definition of reactivity: the variety of steps required to achieve 95% of the optimal average reward ten times, excluding the initial 100 steps.
  3. Arms Allocation: This means the frequency with which each algorithm utilizes the available arms. Presented as a percentage, it reveals the algorithm’s propensity to pick out each arm over time. Ideally, for probably the most efficient pricing strategy, we’d want an algorithm to allocate 100% of its selections to the best-performing arm and 0% to the remainder. Such an allocation would inherently result in a regret value of 0, denoting optimal performance.

Evaluating MAB algorithms poses challenges on account of the highly stochastic nature of their outcomes. Because of this due to inherent randomness in determining quantities, the outcomes can greatly vary from one run to a different. For a strong evaluation, probably the most effective approach is to execute the goal simulation multiple times, accumulate the outcomes and metrics from each simulation, after which compute the common.

The initial step involves making a function to simulate the decision-making process. This function will implement the feedback loop represented within the below image.

Feedback loop implemented within the simulation function

That is the implementation of the simulation loop:

The inputs to this function are:

  • prices: A listing of candidate prices we wish to check (essentially our “arms”).
  • nstep: The overall variety of steps within the simulation.
  • strategy: The algorithm we aim to check for making decisions on the subsequent price.

Lastly, we want to jot down the code for the outer loop. For each goal strategy, this loop will call run_simulation multiple times, collect and aggregate the outcomes from each execution, after which display the outcomes.

For our evaluation, we’ll use the next configuration parameters:

  • prices: Our price candidates → [20, 30, 40, 50, 60]
  • nstep: Variety of time steps for each simulation → 10000
  • nepoch: Variety of simulation executions → 1000

Moreover, by setting our price candidates, we are able to promptly obtain the associated purchase probabilities, that are (roughly) [0.60, 0.44, 0.31, 0.22, 0.15].

After running the simulation we’re finally capable of see some results. Let’s start from the plot of the cumulative regret:

From the graph, we are able to see that TS is the winner when it comes to mean cumulative regret, nevertheless it takes around 7,500 steps to surpass ε-greedy. However, we’ve got a transparent loser, which is UCB1. In its basic configuration, it essentially performs on par with the greedy approach (we’ll get back to this later). Let’s try to grasp the outcomes higher by exploring the opposite available metrics. In all 4 cases, the reactivity shows very large standard deviations, so we’ll deal with the median values as a substitute of the means, as they’re more immune to outliers.

The initial remark from the plots reveals that while TS surpasses ε-greedy when it comes to the mean, it barely lags behind when it comes to the median. Nonetheless, its standard deviation is smaller. Particularly interesting is the reactivity bar plot, which shows how TS struggles to rapidly achieve a good average reward. At first, this was counterintuitive to me, however the mechanism behind TS on this scenario clarified matters. We previously mentioned that TS estimates purchase probabilities. Yet, decisions are made based on the product of those probabilities and the costs. Having knowledge of the true probabilities (that, as mentioned, are [0.60, 0.44, 0.31, 0.22, 0.15]) allows us to calculate the expected rewards TS is actively navigating: [12.06, 13.25, 12.56, 10.90, 8.93]. In essence, although the underlying probabilities differ considerably, the expected revenue values are relatively close from its perspective, especially in proximity to the optimal price. This implies TS requires more time to discern the optimal arm. While TS stays the top-performing algorithm (and its median eventually drops below that of the ε-greedy one if the simulation is prolonged), it demands an extended period to discover the perfect strategy on this context. Below, the arm allocation pies show how TS and ε-greedy do pretty much in identifying the perfect arm (price=30) and using it more often than not throughout the simulation.

Now let’s get back to UCB1. Regret and reactivity confirm that it’s principally acting as a completely exploitative algorithm: quick to get an excellent level of average reward but with big regret and high variability of the final result. If we have a look at the arm allocations that’s much more clear. UCB1 is barely barely smarter than the Greedy approach since it focuses more on the three arms with higher expected rewards (prices 20, 30, and 40). Nonetheless, it essentially doesn’t explore in any respect.

Enter hyperparameter tuning. It’s clear that we want to find out the optimal value of the load C that balances exploration and exploitation. Step one is to switch the UCB1 code.

On this updated code, I’ve incorporated the choice to normalize the common reward before adding the “uncertainty bonus”, which is weighted by the hyperparameter C. The rationale for that is to permit for a consistent search range for the perfect hyperparameter (say 0.5–1.5). Without this normalization, we could achieve similar results, however the search interval would wish adjustments based on the range of values we’re coping with every time. I’ll spare you the boredom of finding the perfect C value; it might probably be easily determined through a grid search. It seems that the optimal value is 0.7. Now, let’s rerun the simulation and examine the outcomes.

That’s quite the plot twist, isn’t it? Now, UCB1 is clearly the perfect algorithm. Even when it comes to reactivity, it has only barely deteriorated in comparison with the previous rating.

Moreover, from the attitude of arm allocation, UCB1 is now the undisputed leader.

  • Theory vs. Experience: Starting with book-based learning is a necessary first step when delving into recent topics. Nonetheless, the earlier you immerse yourself in hands-on experiences, the faster you’ll transform information into knowledge. The nuances, subtleties, and corner cases you encounter when applying algorithms to real-world use cases will offer insights far beyond any data science book you may read.
  • Know Your Metrics and Benchmarks: In the event you can’t measure what you’re doing, you’ll be able to’t improve it. Never begin any implementations without understanding the metrics you propose to make use of. Had I only considered regret curves, I might need concluded, “UCB1 doesn’t work.” By evaluating other metrics, especially arm allocation, it became evident that the algorithm simply wasn’t exploring sufficiently.
  • No One-Size-Matches-All solutions: While UCB1 emerged as the highest selection in our evaluation, it doesn’t imply it’s the universal solution to your dynamic pricing challenge. On this scenario, tuning was straightforward because we knew the optimal value we sought. In real life, situations are never so clear-cut. Do you possess enough domain knowledge or the means to check and adjust your exploration factor for the UCB1 algorithm? Perhaps you’d lean towards a reliably effective option like ε-greedy that guarantees immediate results. Or, you could be managing a bustling e-commerce platform, showcasing a product 10000 times per hour, and also you’re willing to be patient, confident that Thompson Sampling will attain the utmost cumulative reward eventually. Yeah, life ain’t easy.

Finally, let me say that if this evaluation seemed daunting, unfortunately, it already represents a really simplified situation. In real-world dynamic pricing, prices and buy probabilities don’t exist in a vacuum — they really exist in ever-changing environments they usually’re influenced by various aspects. For instance, it’s highly improbable that purchase probability stays consistent all year long, across all customer demographics and regions. In other words, to optimize pricing decisions, we must consider our customers’ contexts. This consideration might be the point of interest of my next article, where I’ll delve deeper into the issue by integrating customer information and discussing Contextual Bandits. So, stay tuned!

LEAVE A REPLY

Please enter your comment!
Please enter your name here