Multiple stopping time POMDPs: Structural results & application in interactive advertising on social media. (September 2018)

• Record Type: Journal Article
• Authors: Krishnamurthy, Vikram; Aprem, Anup; Bhatt, Sujay
• Is Part Of: Automatica. Volume 95(2018)
• Page Start: 385
• Page End: 398
• Publication Date: 2018-09
• Subjects: Partially observed Markov decision process -- Multiple stopping time problem -- Structural result -- Monotone policies -- Stochastic approximation -- Monotone likelihood ratio dominance -- Submodularity -- Live social media -- Scheduling -- Interactive advertisement; Automatic control -- Periodicals; Automation -- Periodicals; 629.805
• DOI: 10.1016/j.automatica.2018.06.013
• Languages: English
• ISSNs: 0005-1098

Abstract

Abstract: This paper considers a multiple stopping time problem for a Markov chain observed in noise, where a decision maker chooses at most L stopping times to maximize a cumulative objective. We formulate the problem as a Partially Observed Markov Decision Process (POMDP) and derive structural results for the optimal multiple stopping policy. The main results are as follows: (i) The optimal multiple stopping policy is shown to be characterized by threshold curves Γ l, for l = 1, …, L, in the unit simplex of Bayesian Posteriors. (ii) The stopping sets S l (defined by the threshold curves Γ l ) are shown to exhibit the following nested structure S l − 1 ⊂ S l . (iii) The optimal cumulative reward is shown to be monotone with respect to the copositive ordering of the transition matrix. (iv) A stochastic gradient algorithm is provided for estimating linear threshold policies by exploiting the structural results. These linear threshold policies approximate the threshold curves Γ l, and share the monotone structure of the optimal multiple stopping policy. (v) Application of the multiple stopping framework to interactively schedule advertisements in live online social media. It is shown that advertisement scheduling using multiple stopping performs significantly better than currently used methods.