Dynamic Pricing with Multi-Armed Bandit: Studying by Doing | by Massimiliano Costacurta | Aug, 2023

Making use of Reinforcement Studying methods to real-world use instances, particularly in dynamic pricing, can reveal many surprises

Within the huge world of decision-making issues, one dilemma is especially owned by Reinforcement Studying methods: exploration versus exploitation. Think about strolling right into a on line casino with rows of slot machines (often known as “one-armed bandits”) the place every machine pays out a unique, unknown reward. Do you discover and play every machine to find which one has the very best payout, or do you stick to at least one machine, hoping it’s the jackpot? This metaphorical state of affairs underpins the idea of the Multi-armed Bandit (MAB) drawback. The target is to discover a technique that maximizes the rewards over a sequence of performs. Whereas exploration gives new insights, exploitation leverages the knowledge you already possess.

Now, transpose this precept to dynamic pricing in a retail state of affairs. Suppose you’re an e-commerce retailer proprietor with a brand new product. You aren’t sure about its optimum promoting value. How do you set a value that maximizes your income? Must you discover totally different costs to grasp buyer willingness to pay, or do you have to exploit a value that has been performing effectively traditionally? Dynamic pricing is actually a MAB drawback in disguise. At every time step, each candidate value level might be seen as an “arm” of a slot machine and the income generated from that value is its “reward.” One other strategy to see that is that the target of dynamic pricing is to swiftly and precisely measure how a buyer base’s demand reacts to various value factors. In less complicated phrases, the intention is to pinpoint the demand curve that finest mirrors buyer conduct.

On this article, we’ll discover 4 Multi-armed Bandit algorithms to guage their efficacy towards a well-defined (although not easy) demand curve. We’ll then dissect the first strengths and limitations of every algorithm and delve into the important thing metrics which might be instrumental in gauging their efficiency.

Historically, demand curves in economics describe the connection between the value of a product and the amount of the product that customers are prepared to purchase. They typically slope downwards, representing the frequent commentary that as value rises, demand sometimes falls, and vice-versa. Consider well-liked merchandise similar to smartphones or live performance tickets. If costs are lowered, extra folks have a tendency to purchase, but when costs skyrocket, even the ardent followers may assume twice.

But in our context, we’ll mannequin the demand curve barely otherwise: we’re placing value towards likelihood. Why? As a result of in dynamic pricing eventualities, particularly digital items or providers, it’s usually extra significant to assume when it comes to the chance of a sale at a given value than to invest on precise portions. In such environments, every pricing try might be seen as an exploration of the chance of success (or buy), which might be simply modeled as a Bernoulli random variable with a likelihood p relying on a given check value.

Right here’s the place it will get notably fascinating: whereas intuitively one may assume the duty of our Multi-armed Bandit algorithms is to unearth that very best value the place the likelihood of buy is highest, it’s not fairly so easy. Actually, our final purpose is to maximise the income (or the margin). This implies we’re not looking for the value that will get the most individuals to click on ‘purchase’ — we’re looking for the value that, when multiplied by its related buy likelihood, offers the very best anticipated return. Think about setting a excessive value that fewer folks purchase, however every sale generates vital income. On the flip aspect, a really low value may appeal to extra consumers, however the complete income may nonetheless be decrease than the excessive value state of affairs. So, in our context, speaking in regards to the ‘demand curve’ is considerably unconventional, as our goal curve will primarily characterize the likelihood of buy somewhat than the demand immediately.

Now, attending to the mathematics, let’s begin by saying that shopper conduct, particularly when coping with value sensitivity, isn’t at all times linear. A linear mannequin may counsel that for each incremental improve in value, there’s a relentless decrement in demand. In actuality, this relationship is usually extra advanced and nonlinear. One strategy to mannequin this conduct is by utilizing logistic features, which might seize this nuanced relationship extra successfully. Our chosen mannequin for the demand curve is then:

Right here, a denotes the utmost achievable likelihood of buy, whereas b modulates the sensitivity of the demand curve towards value adjustments. The next worth of b means a steeper curve, approaching extra quickly to decrease buy possibilities as the value will increase.

For any given value level, we’ll be then capable of receive an related buy likelihood, p. We will then enter p right into a Bernoulli random variable generator to simulate the response of a buyer to a specific value proposal. In different phrases, given a value, we are able to simply emulate our reward operate.

Subsequent, we are able to multiply this operate by the value so as to get the anticipated income for a given value level:

Unsurprisingly, this operate doesn’t attain its most in correspondence with the very best likelihood. Additionally, the value related to the utmost doesn’t rely on the worth of the parameter a, whereas the utmost anticipated return does.

With some recollection from calculus, we are able to additionally derive the method for the by-product (you’ll want to make use of a mixture of each the product and the chain rule). It’s not precisely a calming train, nevertheless it’s nothing too difficult. Right here is the analytical expression of the by-product of the anticipated income:

This by-product permits us to seek out the precise value that maximizes our anticipated income curve. In different phrases, by utilizing this particular method in tandem with some numerical algorithms, we are able to simply decide the value that units it to 0. This, in flip, is the value that maximizes the anticipated income.

And that is precisely what we’d like, since by fixing the values of a and b, we’ll instantly know the goal value that our bandits should discover. Coding this in Python is a matter of some strains of code:

For our use case, we’ll set a = 2 and b = 0.042, which is able to give us a goal value of about 30.44, related to an optimum likelihood of 0.436 ( → optimum common reward is 30.44*0.436=13.26). This value is clearly unknown typically and it’s precisely the value that our Multi-armed Bandit algorithms will search.

Now that we’ve recognized our goals, it’s time to discover varied methods for testing and analyzing their efficiency, strengths, and weaknesses. Whereas a number of algorithms exist in MAB literature, in relation to real-world eventualities, 4 major methods (together with their variations) predominantly kind the spine. On this part, we’ll present a short overview of those methods. We assume the reader has a foundational understanding of them; nevertheless, for these focused on a extra in-depth exploration, references are offered on the finish of the article. After introducing every algorithm, we’ll additionally current its Python implementation. Though every algorithm possesses its distinctive set of parameters, all of them generally make the most of one key enter: the arm_avg_reward vector. This vector denotes the typical reward garnered from every arm (or motion/value) as much as the present time step t. This vital enter guides all of the algorithms in making knowledgeable choices in regards to the subsequent value setting.

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

Grasping: This technique is like at all times going again to the machine that gave you essentially the most cash the primary few instances you performed. After making an attempt out every machine a bit, it sticks with the one which appeared the perfect. However there may be an issue. What if that machine was simply fortunate initially? The Grasping technique may miss out on higher choices. On the brilliant aspect, the code implementation is basically easy:

It’s important to distinguish the preliminary state of affairs (when all rewards are 0) from the common one. Typically, you’ll discover solely the ‘else’ half applied, which certainly works even when all rewards are at 0. But, this strategy can result in a bias towards the primary component. In the event you make this oversight, you may find yourself paying that bias, notably if the optimum reward occurs to be tied to the primary arm (sure, I’ve been there). The Grasping strategy is often the least-performing one and we’ll primarily use it as our efficiency baseline.

ϵ-greedy: The ε-greedy (epsilon-greedy) algorithm is a modification to deal with the principle disadvantage of the grasping strategy. It introduces a likelihood ε (epsilon), sometimes a small worth, to pick out a random arm, selling exploration. With a likelihood 1−ε, it chooses the arm with the very best estimated reward, favoring exploitation. By balancing between random exploration and exploitation of identified rewards, the ε-greedy technique goals to attain higher long-term returns in comparison with purely grasping strategies. Once more, the implementation is rapid, it’s merely an extra ‘if’ on prime of the Grasping code.

UCB1 (Higher Confidence Sure): The UCB1 technique is sort of a curious explorer looking for the perfect restaurant in a brand new metropolis. Whereas there’s a favourite spot they’ve loved, the attract of doubtless discovering a fair higher place grows with every passing day. In our context, UCB1 combines the rewards of identified value factors with the uncertainty of these much less explored. Mathematically, this steadiness is achieved by means of a method: the typical reward of a value level plus an “uncertainty bonus” based mostly on how lengthy because it was final tried. This bonus is calculated as

and represents the “rising curiosity” in regards to the untried value. The hyperparameter C controls the steadiness between exploitation and exploration, with larger values of C encouraging extra exploration of less-sampled arms. By at all times deciding on the value with the very best mixed worth of identified reward and curiosity bonus, UCB1 ensures a mixture of sticking to what’s identified and venturing into the unknown, aiming to uncover the optimum value level for optimum income. I’ll begin with the by-the-book implementation of this strategy, however we’ll quickly see that we have to tweak it a bit.

Thompson Sampling: This Bayesian strategy addresses the exploration-exploitation dilemma by probabilistically deciding on arms based mostly 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: successful will increase the alpha parameter, whereas a failure augments the beta. Throughout every play, TS attracts from the present Beta distribution of every arm and opts for the one with the highest sampled worth. This technique permits TS to dynamically alter based mostly on gathered rewards, adeptly balancing between the exploration of unsure arms and the exploitation of these identified to be rewarding. In our particular state of affairs, though the foundational reward operate follows a Bernoulli distribution (1 for a purchase order and 0 for a missed buy), the precise reward of curiosity is the product of this fundamental reward and the present value underneath check. Therefore, our implementation of TS will want a slight modification (which may even introduce some surprises).

The change is definitely fairly easy: to find out essentially the most promising subsequent arm, samples extracted from the posterior estimates are multiplied by their respective value factors (line 3). This modification ensures choices are anchored on the anticipated common income, shifting the main target from the very best buy likelihood.

At this level, having gathered all the important thing components to assemble a simulation evaluating the efficiency of the 4 algorithms in our dynamic pricing context, we should ask ourselves: what precisely will we be measuring? The metrics we select are pivotal, as they are going to information us within the technique of each evaluating and enhancing the algorithm implementation. On this endeavor, I’m zeroing in on three key indicators:

1. Remorse: This metric measures the distinction between the reward obtained by the chosen motion and the reward that might have been obtained by taking the very best motion. Mathematically, remorse at time t is given by: Remorse(t)=Optimum Reward(t)−Precise Reward(t). Remorse, when accrued over time, offers perception into how a lot we’ve “misplaced” by not at all times selecting the perfect motion. It’s most well-liked over cumulative reward as a result of it offers a clearer indication of the algorithm’s efficiency relative to the optimum state of affairs. Ideally, a remorse worth near 0 signifies proximity to optimum decision-making.
2. Reactivity: This metric gauges the pace at which an algorithm approaches a goal common reward. Basically, it’s a measure of the algorithm’s adaptability and studying effectivity. The faster an algorithm can obtain the specified common reward, the extra reactive it’s, implying a swifter adjustment to the optimum value level. In our case the goal reward is ready at 95% of the optimum common reward, which is 13.26. Nevertheless, preliminary steps can exhibit excessive variability. For example, a fortunate early alternative may end in successful from a low likelihood arm related to a excessive value, rapidly attaining the edge. As a result of such fluctuations, I’ve opted for a stricter definition of reactivity: the variety of steps required to achieve 95% of the optimum common reward ten instances, excluding the preliminary 100 steps.
3. Arms Allocation: This means the frequency with which every algorithm makes use of the obtainable arms. Offered as a proportion, it reveals the algorithm’s propensity to pick out every arm over time. Ideally, for essentially the most environment friendly pricing technique, we’d need an algorithm to allocate 100% of its selections to the best-performing arm and 0% to the remaining. Such an allocation would inherently result in a remorse worth of 0, denoting optimum efficiency.

Evaluating MAB algorithms poses challenges because of the extremely stochastic nature of their outcomes. Which means that due to the inherent randomness in figuring out portions, the outcomes can drastically differ from one run to a different. For a strong analysis, the best strategy is to execute the goal simulation a number of instances, accumulate the outcomes and metrics from every simulation, after which compute the typical.

The preliminary step includes making a operate to simulate the decision-making course of. This operate will implement the suggestions loop represented within the beneath picture.

That is the implementation of the simulation loop:

The inputs to this operate are:

• costs: A listing of candidate costs we want to check (basically our “arms”).
• nstep: The entire variety of steps within the simulation.
• technique: The algorithm we intention to check for making choices on the subsequent value.

Lastly, we have to write the code for the outer loop. For each goal technique, this loop will name run_simulation a number of instances, accumulate and combination the outcomes from every execution, after which show the outcomes.

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

• costs: Our value 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 value candidates, we are able to promptly receive the related buy possibilities, that are (roughly) [0.60, 0.44, 0.31, 0.22, 0.15].

After working the simulation we’re lastly capable of see some outcomes. Let’s begin from the plot of the cumulative remorse:

From the graph, we are able to see that TS is the winner when it comes to imply cumulative remorse, nevertheless it takes round 7,500 steps to surpass ε-greedy. However, we have now a transparent loser, which is UCB1. In its fundamental configuration, it basically performs on par with the grasping strategy (we’ll get again to this later). Let’s attempt to perceive the outcomes higher by exploring the opposite obtainable metrics. In all 4 instances, the reactivity reveals very giant normal deviations, so we’ll concentrate on the median values as a substitute of the means, as they’re extra immune to outliers.

The preliminary commentary from the plots reveals that whereas TS surpasses ε-greedy when it comes to the imply, it barely lags behind when it comes to the median. Nevertheless, its normal deviation is smaller. Notably fascinating is the reactivity bar plot, which reveals how TS struggles to quickly obtain a positive common reward. At first, this was counterintuitive to me, however the mechanism behind TS on this state of affairs clarified issues. We beforehand talked about that TS estimates buy possibilities. But, choices are made based mostly on the product of those possibilities and the costs. Having information of the actual possibilities (that, as talked about, are [0.60, 0.44, 0.31, 0.22, 0.15]) permits us to calculate the anticipated rewards TS is actively navigating: [12.06, 13.25, 12.56, 10.90, 8.93]. In essence, though the underlying possibilities differ significantly, the anticipated income values are comparatively shut from its perspective, particularly in proximity to the optimum value. This implies TS requires extra time to discern the optimum arm. Whereas TS stays the top-performing algorithm (and its median ultimately drops beneath that of the ε-greedy one if the simulation is extended), it calls for an extended interval to determine the perfect technique on this context. Beneath, the arm allocation pies present how TS and ε-greedy do fairly effectively in figuring out the perfect arm (value=30) and utilizing it more often than not throughout the simulation.

Now let’s get again to UCB1. Remorse and reactivity affirm that it’s principally performing as a totally exploitative algorithm: fast to get a very good stage of common reward however with massive remorse and excessive variability of the result. If we take a look at the arm allocations that’s much more clear. UCB1 is simply barely smarter than the Grasping strategy as a result of it focuses extra on the three arms with larger anticipated rewards (costs 20, 30, and 40). Nevertheless, it basically doesn’t discover in any respect.

Enter hyperparameter tuning. It’s clear that we have to decide the optimum worth of the burden C that balances exploration and exploitation. Step one is to change the UCB1 code.

On this up to date code, I’ve integrated the choice to normalize the typical reward earlier than including the “uncertainty bonus”, which is weighted by the hyperparameter C. The rationale for that is to permit for a constant search vary for the perfect hyperparameter (say 0.5–1.5). With out this normalization, we might obtain comparable outcomes, however the search interval would want changes based mostly on the vary of values we’re coping with every time. I’ll spare you the boredom of discovering the perfect C worth; it may be simply decided by means of a grid search. It seems that the optimum worth is 0.7. Now, let’s rerun the simulation and study the outcomes.

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

Moreover, from the angle of arm allocation, UCB1 is now the undisputed chief.

• Idea vs. Expertise: Beginning with book-based studying is a necessary first step when delving into new subjects. Nevertheless, the earlier you immerse your self in hands-on experiences, the sooner you’ll remodel data into information. The nuances, subtleties, and nook instances you encounter when making use of algorithms to real-world use instances will provide insights far past any knowledge science guide you may learn.
• Know Your Metrics and Benchmarks: In the event you can’t measure what you’re doing, you’ll be able to’t enhance it. By no means start any implementations with out understanding the metrics you propose to make use of. Had I solely thought of remorse curves, I may need concluded, “UCB1 doesn’t work.” By evaluating different metrics, particularly arm allocation, it grew to become evident that the algorithm merely wasn’t exploring sufficiently.
• No One-Dimension-Matches-All options: Whereas UCB1 emerged because the best choice in our evaluation, it doesn’t suggest it’s the common answer to your dynamic pricing problem. On this state of affairs, tuning was easy as a result of we knew the optimum worth we sought. In actual life, conditions are by no means so clear-cut. Do you possess sufficient area information or the means to check and alter your exploration issue for the UCB1 algorithm? Maybe you’d lean in direction of a reliably efficient possibility like ε-greedy that guarantees rapid outcomes. Or, you may be managing a bustling e-commerce platform, showcasing a product 10000 instances per hour, and also you’re prepared to be affected person, assured that Thompson Sampling will attain the utmost cumulative reward ultimately. Yeah, life ain’t simple.

Lastly, let me say that if this evaluation appeared daunting, sadly, it already represents a really simplified state of affairs. In real-world dynamic pricing, costs and buy possibilities don’t exist in a vacuum — they really exist in ever-changing environments and so they’re influenced by varied elements. For instance, it’s extremely inconceivable that buy likelihood stays constant all year long, throughout all buyer demographics and areas. In different phrases, to optimize pricing choices, we should think about our prospects’ contexts. This consideration would be the focus of my subsequent article, the place I’ll delve deeper into the issue by integrating buyer data and discussing Contextual Bandits. So, keep tuned!