An online retailer selling a perishable product must decide how much to bid for sponsored-search clicks and what discount to offer on a bundle with an always-available item. A new arXiv study presents a posterior-sampling agent that learns about both customer demand and the response of clicks to its bids while making those decisions over repeated selling seasons.
The problem is complicated by gaps in the data created by the retailer’s own choices. With no bid, the seller receives no information about paid clicks, and it observes customers’ purchase choices only after they arrive through a click. If the retailer concludes too early that advertising is ineffective and stops bidding, it may never gather evidence that would change that belief. Changes to bundle discounts can also lead customers to wait for a better offer, making their delayed purchases look like lost sales.
The agent maintains a posterior distribution over possible markets and click-response patterns. Each period, it samples a candidate market and uses a precomputed, exactly solved season plan for that candidate to choose a bid and discount. The researchers tested the approach in a simulated online florist, comparing it with other learning and exploration strategies.
Sampling a new market each period produced the lowest average regret in the reported tests: $33.6 over 500 seasons, compared with $74.0 for a planner using point estimates and $109.4 for an approach that sampled once per season. In weak markets, the period-by-period agent gave up 12% to 23% of the revenue a fully informed seller could earn in one season over the 500-season run. That was four to seven times less than the loss reported for sampling once per season.
The study also found that a point-estimate planner can become stuck bidding nothing. Under a prior that assigned only 2% probability to responsive click curves, it never began bidding and lost more than half of the fully informed seller’s revenue each season. The posterior-sampling agent began bidding after about three seasons on average, compared with around 50 seasons for the once-per-season version.
The authors report that discount learning may be unnecessary when displayed low stock keeps customers’ willingness to pay above the posted price. However, frequent customer waiting can distort the agent’s market estimates, because delayed purchases appear as no-sales. Keeping the discount fixed for an entire season removes this waiting effect in the study, at a cost of 5.9% of fully informed revenue in a weak market and no loss in a strong one.
Sources: arXiv cs.AI.