Sequential Sponsored-Products and Off-Amazon Advertising Optimization for Etailers

Abstract

Sponsored-products (SP) advertising is a popular way to promote products on Amazon. Etailers who have a large catalog of products often create SP ad groups for products with similar attributes. An SP ad group consists of a set of products that share a same keyword set used for product search. In addition to SP ads, etailers may link to external websites for advertising their products, which is called off-Amazon (OA) ads. This study focuses on the optimization of sequential SP and OA (abbreviated as SSPOA) ads decisions for etailers. We model the SSPOA optimization as a controlled Markovian multi-armed bandit (MAB) process. When the mean sales volume per unit time (i.e., sales rate) for each product is known, we characterize the etailer’s optimal SSPOA policy for products in an ad group. When the parameters of the sales rates are unknown, we develop a Thompson-sampling-based algorithm that couples the SP and OA ads decisions. We prove that the regret bound of the proposed algorithm is $\tilde{O} (\sqrt{T})$ , where $T$ is the total horizon length. Compared with existing literature, our problem additionally considers the regret from applying the estimated control policy and the impacts of choosing non-optimal keyword sets on subsequent states. We also conduct numerical experiments that validate our theoretical results. Moreover, we extend the base model in several directions, that is, considering unknown transition rates between different sales rate levels, incorporating correlated keyword sets, and learning the optimal policy using Posterior Sampling for reinforcement learning under a discretized setting.

Keywords

Sequential Sponsored-Products (SP) and Off-Amazon (OA) Advertising Keyword Set Selections Controlled Markovian Multi-Armed Bandit Process Thompson Sampling Regret Bound Analysis

Get full access to this article

View all access options for this article.

References

Agrawal

Asawa

(2019) Decentralized learning for opportunistic spectrum access: Multiuser restless multiarmed bandit formulation. IEEE Systems Journal 14(2): 2485–2496.

Agrawal

Goyal

(2012) Analysis of Thompson sampling for the multi-armed bandit problem. In: Proceedings of the 25th Annual Conference on Learning Theory, Vol. 23, Edinburgh, Scotland, pp.39.1–39.26. PMLR.

Agrawal

Goyal

(2013) Further optimal regret bounds for Thompson sampling. In: Proceedings of the 16th International Conference on Artificial Intelligence and Statistics, Scottsdale, Arizona, USA, Vol. 31, pp.99–107. PMLR.

Alessandro

Gans

Chick

(2013) Optimal hiring and retention policies for heterogeneous workers who learn. Management Science 60(1): 110–129.

Amazon Ads (2023) Sponsored products Ad groups. Available at: https://advertising.amazon.com/API/docs/en-us/guides/overview (last accessed date 29 December 2025).

Auer

Cesa-Bianchi

Freund

(2002) The nonstochastic multiarmed bandit problem. SIAM Journal on Computing 32(1): 48–77.

Baltrukenaite

(2023) 10 Best Sales Targets for 2023: How to Reach Your Sales Goals. Plecto. Available at: https://www.plecto.com/blog/sales-performance/sales-target/ (last accessed date 29 December 2025).

Banjević

Kim

(2019) Thompson sampling for stochastic control: The continuous parameter case. IEEE Transactions on Automatic Control 64(10): 4137–4152.

Carlsson

Dubhashi

Johansson

(2021) Thompson sampling for bandits with clustered arms. Available at: https://arxiv.org/2109.01656.

10.

Cella

Pontil

Gentile

(2021) Best model identification: A rested bandit formulation. In: Proceedings of the 38th International Conference on Machine Learning, Vol. 139, Virtual Conference / Online (hosted by Vienna, Austria), pp.1362–1372. PMLR.

11.

Chen

Jian

Yongbo

(2007) Optimal control of selling channels for an online retailer with cost-per-click payments and seasonal products. Production and Operations Management 16(3): 292–305.

12.

Commission Factory (2023) Affiliate standard terms. Available at: https://legal.commissionfactory.com/affiliate-standard-terms (last accessed date 29 December 2025).

13.

Connolly

(2022) Amazon sponsored products Ads 2022 guide. JungleScout. Available at: https://www.junglescout.com/blog/amazon-sponsored-product-ads/ (last accessed date 29 December 2025).

14.

Cowen and Company (2017) Channels where US internet users complete purchases from brands discovered on facebook. Available at: https://www.insiderintelligence.com/chart/217015/ (last accessed date 29 December2025).

15.

Ferreira

Simichi-Levi

Wang

(2018) Online network revenue management using Thompson sampling. Operations Research 66(6): 1586–1602.

16.

Frankenfield

(2022) Affiliate marketer: Definition, examples, and how to get started. Investopedia. Available at: https://www.investopedia.com/terms/a/affiliate-marketing.asp (last accessed date 29 December 2025).

17.

Gopalan

Mannor

(2015) Thompson sampling for learning parameterized Markov decision processes. In: Proceedings of The 28th Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 40, Paris, France, pp.861–898. PMLR.

18.

Grünewälder

Khaleghi

(2019) Approximations of the restless bandit problem. Journal of Machine Learning Research 20(14): 1–37.

19.

Gupta

Chaudhari

Joshi

Yaan

(2021) Multi-armed bandits with correlated arms. IEEE Transactions on Information Theory 67(10): 6711–6732.

20.

Kim

(2017) Thompson sampling for stochastic control: The finite parameter case. IEEE Transactions on Automatic Control 62(12): 6415–6422.

21.

Navarro

(2020) 11 Amazon advertising mistakes to avoid. Available at: https://www.searchenginejournal.com/amazon-advertising-mistakes/344459/ (last accessed date 29 December 2025).

22.

Niño-Mora

(2002) Dynamic allocation indices for restless projects and queueing admission control: A polyhedral approach. Mathematical Programming 93(3): 361–413.

23.

Niño-Mora

(2023) Markovian restless bandits and index policies: A review. Mathematics 11(7): 1–27.

24.

Osband

Russo

Van Roy

(2013) (More) efficient reinforcement learning via posterior sampling. In: Proceedings of the 27th International Conference on Neural Information Processing Systems, Vol. 2, Red Hook, NY, USA, pp.3003–3011. Curran Associates Inc.

25.

Ouyang

Gagrani

Nayyar

Jain

(2017) Learning unknown Markov decision processes: A Thompson sampling approach. In: Proceedings of the 31st International Conference on Neural Information Processing Systems, Vol. 30, Paris, France, pp.1333–1342. PMLR.

26.

Pandey

Chakrabarti

Agarwal

(2007) Multi-armed bandit problems with dependent arms. In: Proceedings of the 24th International Conference on Machine Learning, New York, NY, USA, pp.721–728. Association for Computing Machinery.

27.

Petrov

(2023) 47 Amazon statistics to bedazzle you in 2023. Techjury. Available at: https://techjury.net/blog/amazon-statistics/ (last accessed date 29 December 2025).

28.

Ronald

Daniil

Peter

Munos

(2014) Regret bounds for restless Markov bandits. Theoretical Computer Science 558(13): 62–76.

29.

Tapfiliate (2024) Affiliate conversion tracking: Everything you need to know. Available at: https://tapfiliate.com/blog/affiliate-conversion-tracking/ (last accessed date 29 December 2025).

30.

Tekin

Liu

(2011) Adaptive learning of uncontrolled restless bandits with logarithmic regret. In: 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp.983–990.

31.

Tekin

Liu

(2012) Online learning of rested and restless bandits. IEEE Transactions on Information Theory 58(8): 5588–5611.

32.

Thackston

(2020) How to promote Amazon products offsite to increase traffic and sales. Marketing Words. Available at: https://www.marketingwords.com/blog/promote-amazon-products/ (last accessed date 29 December 2025).

33.

Thompson

(1933) On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25(3/4): 285–294.

34.

Whittle

(1988) Restless bandits: Activity allocation in a changing world. Journal of Applied Probability 0: 287–298.

35.

Word Stream (2023) Ad groups: How to create more effective ad groups for PPC. Available at: https://www.wordstream.com/ad-groups (last accessed date 2 December 2025).

36.

Xiong

Singh

(2022) Reinforcement learning augmented asymptotically optimal index policy for finite-horizon restless bandits. Proceedings of the AAAI Conference on Artificial Intelligence 36(8): 8726–8734.

37.

Chen

Tang

(2021) An online algorithm for the risk-aware restless bandit. European Journal of Operational Research 290(2): 622–639.

38.

Tewari

(2020) Reinforcement learning in factored MDPs: Oracle-efficient algorithms and tighter regret bounds for the non-episodic setting. Advances in Neural Information Processing Systems 33: 18226–18236.

39.

Yang

(2023) Keyword decisions in sponsored search advertising: A literature review and research agenda. Information Processing and Management 60(1): 103–142.

40.

Zhao

Jiang

Tandon

(2020) Regret analysis of stochastic multi-armed bandit problem with clustered information feedback. In: 2020 International Joint Conference on Neural Networks (IJCNN), pp.1–8. IEEE.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

0.47 MB