Logistic Markov Decision Processes

1 Introduction

Online and mobile interaction with users has been transformed by the use of machine learning (ML) to predict user intent, preferences and responses. However, current methods largely focus on myopic prediction-predicting a user's immediate response to the system's action-without explicitly modeling long-term impact nor addressing the ultimate need to plan sequences of interactions with a user. For example, ad systems typically determine which ads to show based on a current prediction of a user's click probability. Evidence is mounting that myopic predictors compromise user satisfaction and system performance by ignoring long-term value [Hohnhold et al., 2015]. While sequential models of user interaction using Markov decision processes (MDPs) and reinforcement learning (RL) have received increasing attention [Charikar et al., 1999; Li et al., 2009; Archak et al., 2010; 2012; Amin et al., 2012; Silver et al., 2013; Theocharous et al., 2015], they have yet to find widespread adoption due to challenges with modeling and computational scalability.

In this work, we develop a practical approach to optimizing long-term interactions with users by introducing the logistic MDP, a novel form of MDP that incorporates a logistic predictor of a user response variable (such as click probability) into an MDP. Two key insights motivate the development

∗Work performed while author was a visiting intern at Google.

†Work performed while author was a visiting scholar at Google.

Dale Schuurmans†

University of Alberta daes@ualberta.ca

Tyler Lu

Google Research tylerlu@google.com

of logistic MDPs. First, the features used in (myopic) logistic predictors of user responses typically provide a sufficient statistic of user history well suited to (some forms of) long-term modeling. Second, the evolution of the features used in such models often exhibits considerable conditional independence, allowing for compact expression of a transition function as a dynamic Bayesian network (DBN) [Dean and Kanazawa, 1989; Boutilier et al., 1999] that incorporates the predictor into the dynamics.

Once logistic MDPs are motivated and defined, we turn our attention to effectively solving such MDPs in a scalable fashion. Two key obstacles are created by the logistic user response model when devising algorithms that exploit the conditional independence in the dynamics: (i) variable coupling, and (ii) non-linearity introduced. We develop an approximate linear programming (ALP) solution method [Guestrin et al., 2003; de Farias and Van Roy, 2003] that overcomes these obstacles. We do so by developing constraint generation strategies [Schuurmans and Patrascu, 2001] that search for violated constraints using a set of Boolean optimization problems (BOPs) defined over approximations of the logistic function. We provide exact and approximate ALP algorithms for logistic MDPs, and derive error bounds for the approximate algorithms. We demonstrate the effectiveness of the approach on large models, derived from in-app display advertising data, with up to 254 states and 239 actions.

2 Background

The prediction of user responses to recommendations, ads, or other interventions, are routinely tackled using ML. Such predictions are often binary (e.g., will an ad be clicked or an app downloaded) with the predicted probability of responseused to score potential actions (e.g., which ad to show)- often combined with other factors, such as an advertiser's bid. Many models have been used for such prediction, ranging from logistic regression [Richardson et al., 2007; Graepel et al., 2010; McMahan et al., 2013] to deep models [Covington et al., 2016; Cheng et al., 2016].

Since linear logistic regression is the current workhorse for predicting user responses to online ads, we focus on these models in this work. 1 We assume a finite set of variables X = {X1, . . . ,Xn} describing properties of the interaction (e.g., geolocation, age, purchase activity, device), ad (e.g., advertiser, product type), context (e.g., site, app), and user history (e.g., count of past ad impressions, clicks). As is typical in practice, we also assume each Xi has a discrete domain Dom(Xi) and that a "one-hot" encoding is used to transform elements of Dom(X) into a sparse binarized feature vector of length ∑i |Dom(Xi)|. Let ϕ be a binary user response variable (e.g., user click on an ad). Given a learned weight vector u, a linear logistic predictor models the probability of a positive user response to a given feature vector x as:

1 We briefly discuss extensions of our approach to deep neural network models (DNNs) in the concluding section.

In ad settings, we refer to this as a pCTR model.

Sequential models of user behavior in advertising have been studied [Charikar et al., 1999; Archak et al., 2010; Li et al., 2009], though not extensively in practice. Recently, MDP models for optimizing ad serving and promotions have been proposed [Archak et al., 2012; Silver et al., 2013; Theocharous et al., 2015], and temporal models for recommender systems have also received some attention [Shani et al., 2005; Taghipour et al., 2007; Rendle et al., 2010; He and McAuley, 2016; Sahoo et al., 2012; Tan et al., 2016; Wu et al., 2017]. Unfortunately, these methods have yet to find their way into practical recommender and ad serving systems, since realistic models of user dynamics are difficult to learn or specify in practice, and computing optimal behaviour policies in such models is computationally complex, whether by explicitly solving an MDP or via reinforcement learning.

3 Logistic MDPs

To overcome the challenges described above, we introduce a newMDPmodel, logisticMDPs, that extends standardMDPs by introducing a logistic user response variable.

3.1 Non-myopic Models of User Interactions

As noted above, most systems for ad serving or content/product recommendations are myopic in two distinct senses. First, they predict a user's response to a system action (e.g., ad served) without considering the action's impact on subsequent interactions. Second, the prediction is often for some immediate user response (e.g., pCTR) rather than longterm behavior (cumulative click rate, user satisfaction, etc.). This is problematic for several reasons. Intuitively, system actions at a given time will also influence user responses to future actions; e.g. display ad exposure may increase a user's propensity to click on the related ads by increasing awareness through exposure, or may decrease this propensity by creating a "blindness" effect [Hohnhold et al., 2015]. Additionally, an action and user response usually changes the user feature vector used for the next prediction, hence influences the predicted effectiveness of all subsequent actions.

Since the aim is not to optimize a single user interaction, but to do so over (say) a session, week, or lifetime, it is natural to model this engagement with an MDP. One can then construct an optimal policy by directly solving the MDP [Archak et al., 2012; Amin et al., 2012; Boutilier and Lu, 2016], or applying RL to interaction data [Silver et al., 2013; Theocharous et al., 2015].

In this work, we focus on solving an MDP model directly. One reason is that long-term optimization often induces tradeoffs among different objectives that should be encoded in the reward function. 2 Quantifying these tradeoffs precisely in a reward function can be difficult a priori. Model-based methods allow decision makers to efficiently explore the tradeoffs arising from different reward functions. In addition to being used directly, model-bsaed solutions computed offline can be used to accelerate (online or offline) RL.

However, such an approach requires a transition model that captures the dynamics of user behavior (expected user actions, evolution of user state, user responses to actions, etc.). A key challenge is specifying the state space; i.e., defining an appropriate set of features, observable from logged interactions, that adequately summarizes user history in a way that is both predictive of future behavior and renders the implied dynamics Markovian.

Constructing a Model of Interaction Dynamics Fortunately, one does not need to start from scratch. Instead, we leverage the existing myopic predictors of user response as follows. Focusing on logistic regression, a typical model is illustrated in Fig. 1(a), where the response variable ϕ (e.g., representing a positive ad click) depends on the variables Xi representing the user state, user history and relevant context (e.g., web site visited, query issued, app being used, etc.), and variables Ai reflecting various properties of the system action (e.g., ad being shown, app or video being recommended). If we seek to optimize the clicks accumulated during a user session, we must predict not only how actions influence the immediate response, but how they change the variable values we expect to encounter subsequently. Fig. 1(b) illustrates how the myopic response model can be extended to accommodate such dynamics, where we view the variables Xi as state variables and the variables Ai as action variables. The model shows how the state variables at time t+1 depend (probabilistically) on the state at time t, the action taken at time t, and the user's response to that action.

This provides a natural, practical way to construct the required MDP model of user dynamics, which exploits two key characteristics of typical (myopic) responsemodels. First, the features in the myopic model provide a suitable summary of history (i.e., form a sufficient statistic) for predicting response variable ϕ. Second, the features themselves are (roughly) "self-predictive;" i.e., the features at time t (together with ϕ) are often sufficient to predict each state variable Xi. In many practical models, this assumption holds (e.g., some variables reflect static user properties, others capture summary statistics of past user behavior, while still others model the natural evolution of user actions). As a result, one can readily develop models reflecting the evolution of these variables from historical interaction data (assuming sufficient "explicit" exploration or other induced randomness)-indeed, the same logged data used to construct myopic response models can be used directly for this purpose. Finally, the prediction of (the distribution of) state variables Xi at time t + 1 often depends on only a small number of preceding state/action features and (sometimes) the response variable.

2 For instance, in app recommendations, install rate, user app engagement (post-install), revenue generation potential for the developer, and many other factors may play a role.

3.2 Logistic MDPs: Formal Model

We formalize these intuitions in the logistic MDP model, a form of factored MDP using a typical DBN representation [Boutilier et al., 1999] in which the DBN is augmented with the response variable ϕ.

Markov Decision Processes A (finite) MDP [Puterman, 1994] is given by: a finite state space S and action space A; a stochastic transition model P, with P(s, a, s′ ) = pass′ denoting the probability of a transition from state s to s′ when action a is taken; and a bounded, real-valued reward function R(s, a) = ra s denoting the immediate (expected) reward of taking action a at state s. A (stationary, deterministic) policy π specifies an action π(s) ∈ A to be taken in any state s. We seek an optimal policy that maximizes the expected sum of discounted rewards (with discount factor 0 ≤ γ < 1). The (unique) optimal value function V ∗ : S → R satisfies the Bellman equation (2), and induces the optimal policy (3), for all s ∈ S:V ∗ (s) = max

Given an arbitrary (not necessarily optimal) value function (VF) V : S →R, the action-value backup is:

In this work we use linear programming (LP) to solve MDPs [Puterman, 1994]. For a finite MDP, the primal LP formulation is:min

where variables vs reflect the optimal VF at each state s, Qv (·, a) is the action-value backup (treating variable vector v as a VF), and state weighting function α is usually interpreted as the initial state distribution. 3

Factored MDPs In realistic settings, MDPs are specified using finite sets of state and action variables, X =

3 Any strictly positive vector α suffices. The role of the state weighting is less straightforward in approximate linear programming (next section) [de Farias and Van Roy, 2003].

{X1, . . . ,Xn} and A = {A1, . . . ,Am}, respectively. Each state variable Xi has finite domain Dom(Xi) (similarly for action variables). Since the induced state and action spaces, S = Dom(X) and A = Dom(A), have exponential size, DBNs are often used to compactly represent system dynamics [Dean and Kanazawa, 1989; Boutilier et al., 1995; 1999]. Two assumptions allow for the compact representation of the successor state distributions Pr(x(t+1) |x(t) , a(t) ) using a standard DBN (ignoring ϕ for now): (i) they are products of marginals over the individual state variables; 4 and (ii) each variable Xi's local distribution is dependent on a small parent set Pari ⊂ X ∪A. This means that the local distributions themselves can be specified compactly.

Logistic MDPs We augment the standard DBN representation with the binary response variable as follows. 5 We assume the state-action pair (x(t) , a(t) ) at time t determines Pr(ϕ(t+1) ), and the triple (x(t) , a(t) , ϕ(t+1) ) dictates the next state distribution Pr(x(t+1) ). Hence the dynamics factor as:

We assume Pr(x(t+1) |x(t) , a(t) , ϕ(t+1) ) is a product distribution over the t + 1 state variables, with Pr(X(t+1) j |Par (t) j , ϕ(t+1) ) depending on a small set of parents. 6 Pr(ϕ(t+1) |x(t) , a(t) ) is given by the logistic model in (1). Fig. 1(b) illustrates the dependence structure.

The reward function is also assumed to be factored, decomposing as the sum of r reward factors ρi:

where each Ri ⊂ X ∪A is small set of state/action variables, such that x[U] (resp., a[U]) denotes the restriction of a variable instantiation to the subset U ⊆ X ∪A. Unlike traditional factored MDPs, reward factors may also depend on ϕ.

This transition model is very compact, with the local distribution for each Xi having O(|Dom(Pari)||Dom(Xi)|) parameters, while ϕ requires O(∑i Dom(Xi)) parameters. However, as shown in Fig. 1(b), unlike a typical DBN, ϕ correlates all of the t + 1 variables to which it is connecteddestroying the structure that is normally exploited in DBN MDP algorithms. We address this issue next.

4 ALP for Logistic MDPs

The reward and transitions structure of the usual DBN representation of an MDP can be exploited by various solution algorithms [Boutilier et al., 1995; Hoey et al., 1999; St-Aubin et al., 2000; Boutilier et al., 1999]. In this work, we focus on approximate linear programming (ALP) for factored MDPs [Guestrin et al., 2003; Schuurmans and Patrascu, 2001], where the value function is approximated using a linear combination of basis functions or "features" B = {β1, . . . , βk} over X. Here, each βi is a function of some small set Bi ⊂ X, where we assume a bias factor βbias = 1 ∈ B. The resulting value function (VF) is parameterized by a weight vector w:

4 Our approaches also allow correlations among post-action variables, but to simplify notation, we assume full independence (conditional on the prior state and action).

5 Technically, the resulting model remains a DBN, but since the response variable destroys much of the structure typically assumed in a DBN, we treat it differently from other variables.

6 Any specific Xj may be independent of ϕ, but if not, we sometimes refer to ϕ as a parent of Xj .

where B = [β1, . . . , βk] is the basis matrix, and Bx denotes the row of B corresponding to state x. When the weighting function α is factored similarly, the LP becomes: 7

where h(x, a;w) = QV (x, a;w) - V (x;w). Note that the constraint for each state-action pair has a compact representation, since V (x;w) is given by (9), and QV (x, a;w) is a reward term plus an expectation of a linear combination of basis functions. For each βi, denote its backprojection by:

Hence βi depends only on variables in ParBi = ∪Xj∈Bi Parj [Boutilier et al., 1995; Guestrin et al., 2003]. V and QV can be combined to yield

so the LP has a concise objective and constraints.

To handle the exponential number of constraints, we use ALP with constraint generation (ALPCG) [Schuurmans and Patrascu, 2001], where a relaxed LP (the master) is repeatedly solved using a subset of the constraints C ⊆ (X,A). In particular, given the solution w to the master LP, detecting the maximally violated constraint (MVC) is a Boolean optimization problem (BOP):

The subproblem uses Boolean (indicator) variables to express the assignment of state and action variables in x and a, as well as the selection of terms in the sub-functions gi, βi, ρj, with constraints enforcing the consistency of the assignments. The BOP can be solved using a standard Boolean or mixed integer solver. At each iteration the MVC is added to C, tightening the relaxation, and the master LP is re-solved. If no violated constraint exists, the current solution is optimal.

This approach can be very effective for MDPs with compact DBN representations [Schuurmans and Patrascu, 2001], and by terminating ALPCG early, one can further approximate the solution of the MDP.

7 Any compact factorization of the weighting function sufficeswe assume this specific form for ease of exposition.

ALPCG for Logistic MDPs To extend ALPCG to logistic MDPs we need to overcome two complications in the constraint generation subproblem: the loss of conditional independence among state variables, and the non-linearity of the response model in the state-action space.

Using the VF representation (9), the action-value backup now has the form:

where the backprojection gi for basis function βi is defined as in (12), but where we fix ϕ and then take an expectation w.r.t. its realizations (⊤ or ⊥). The same conditioning applies to the reward component ρj of the action-value backup. Thus, the constraint function h can be re-expressed as

An ALP for the logistic MDP can therefore be expressed with the same objective (10) as before, but with the constraint:

This LP has the same desirable features as the ALP formulation for standard DBNs: a compact objective and compact constraints. As with standard ALPCG, we handle the exponential number of constraints using constraint generation.

Search for Maximally Violated Constraints We now turn to the constraint generation problem. Assuming the ALP above has been solved using only a subset of the constraints (17), we wish to find an MVC at the current solution:

Let f(x, a) denote the linear function of state-action features that is passed through the sigmoid in the logistic regression response model (1); that is, Pr(ϕ = ⊤|x, a) = σ(f(x, a)). For any interval [fℓ, fu] of the input space to the sigmoid, we (ab)use the same notation to denote the set of states: [fℓ, fu] = {(x, a) : fℓ ≤ f(x, a) ≤ fu}.

We now define a search procedure to solve (19). Our search for an MVC proceeds by recursively searching in intervals [fℓ, fu] for an MVC among pairs (x, a) ∈ [fℓ, fu]. We call the ALP procedure using this search ALP-SEARCH.

The search for an MVC in interval [fℓ, fu] is complicated by the non-linearity of the constraint function C(x, a;w) in (18). However, if we replace Pr(ϕ|x, a) by some constant σ∗ for all (x, a) ∈ [fℓ, fu], then the optimization (19) to find an MVC over the interval becomes linear:

Since σ(z) is monotonically increasing in z, the quantity σu = σ(fu) provides an upper bound on Pr(ϕ|x, a) for any (x, a) ∈ [fℓ, fu] (see Fig. 2 for an illustration).

The search for the MVC within [fℓ, fu], as embodied in Eqs. (20-21), can be decomposed into a search over two disjoint classes of state-action pairs:

By restricting the search to H+ w , and setting the constant probability term to σu, we obtain the BOP:

A solution of this problem provides a maximizer (x∗u , a∗u ) with objective value U ∗ u . Similarly, the optimization using Hw and the lower bound probability σℓ = σ(fℓ) provides an analogous solution (x∗ℓ , a∗ℓ ) with objective value U ∗ ℓ .

Using the monotonicity of the objective w.r.t. σ, it can be shown that U ∗ = max(U ∗ ℓ ,U ∗ u ) is an upper bound on the maximal constraint violation in [fℓ, fu] (we denote by MCV(I) the maximum degree of constraint violation in interval I). If the corresponding solution is (x∗ , a∗ ), the true violation C(x∗ , a∗ ;w) is a lower bound on MCV([fℓ, fu]). The gap U ∗ -C(x∗ , a∗ ; w) indicates how close it is to provably being the MVC within [fℓ, fu].

This allows us to define conditions under which we can terminate the search: (i) if U ∗ ≤ ε, for some small tolerance ε, there is no violation larger than ϵ in this interval; (ii) if U ∗ ≤ MCV(I), for some other interval I, the MVC (for the full subproblem) does not lie in this interval; (iii) if U ∗ ≤ C(x∗ , a∗ ;w) + ε, then (x∗ , a∗ ) is (within ε of) the MVC in this interval. Should none of these conditions hold, we split the interval and recursively search in the two subintervals [fℓ, fℓ+fu 2 ] and [ fℓ+fu 2 , fu]. When the subproblem search terminates with an MVC (x∗ , a∗ ), we add the true constraint to the master, i.e., 0 ≥ C(x∗ , a∗ ;w), not the approximate constraint using the approximated probability.

ALP-SEARCH will terminate with the identification of a violated constraint if one exists with degree at least ε. Thus, the final master LP may not include all violated constraints; but any unexpressed constraint is within ε of being satisfied. We analyze the error of this relaxation below. Furthermore, it will never generate a constraint that is not violated, so the master LP will never be overconstrained.

ALP-SEARCH can be modified easily to produce an exact solution to the subproblem using a simple identical witness test. When searching in interval [fℓ, fu], the following test ensures the identified constraint is the true MVC in the interval: if the same state-action pair maximizes the degree of constraint violation using both constant probabilities σu and σℓ, we can terminate with that constraint. This test can be implemented by solving two BOPs, over all (x, a) ∈ [fℓ, fu], with constant probabilities σu and σℓ, respectively.

Observation 1. ALP-SEARCHwith the identical witness test constructs an exact solution to the ALP optimization problem.

As a result, an exact solution to for ALP-SEARCH is viable. However, we expect small approximation tolerances to encourage much faster convergence in practice.

A Piecewise Constant Approximation The CG procedure above provides an "exact" solution (modulo termination tolerance ε) to the subproblem by solving a sequence of BOPsthe formulation of one BOP depends on the results of a previous BOP. The same linearization, using a constant approximation for the (sigmoid) response probability over intervals I = [fℓ, fu], can be applied non-adaptively. We can fix a set of intervals in f-space, and approximate the sigmoid in each interval with a constant σI . Such a piecewise-constant (PWC) approximation allows us to compute the MVC within each interval using a single BOP; and since the interval subproblems are independent, they can be solved in parallel. We call ALP using this means of constraint generation ALP-APPROX.

More precisely, we partition f-space into m intervals [δi-1, δi], 1 ≤ i ≤ m, and associate a constant response probability σi with [δi-1, δi], where σi = σ(fi) for some fi ∈ [δi-1, δi]; see Fig. 3. We require only that δ0 ≤ minx,a f(x, a) and δm ≥ maxx,a f(x, a). As above, the search for the MVC in [δi-1, δi] is now linear:

Unlike ALP-SEARCH, we do not refine these intervals, but use a suitably chosen partitioning and fixed σi for each interval. We solve the subproblem for each interval I independently to obtain an approximate MVC (xI , aI ), compute the true degree of violation C(xI , aI ; w) for each candidate, and return to the master the (true) constraint whose true violation is maximal. If the maximum is non-positive, we report no violated constraint and terminate the master.

This CG procedure generally incurs some error, since it may fail to detect a violated constraint for two reasons. First, the PWC approximation for some I may find no violations in I even though a violation exists whose degree has been underestimated. Second, while it may detect a violating stateaction pair using the approximation, if the true violation value for this pair is non-positive, the procedure will claim no violation exists; yet a different state-action pair might exhibit a true violation in I. If this occurs in all intervals, no violated constraint will be added and the master will terminate. 8 We bound the error induced by such a failed detection below.

A key advantage of ALP-APPROX is that the subproblems for distinct intervals are independent and can be solved in parallel. This stands in contrast with exact ALP-SEARCH, where refined subproblems must be solved in sequence.

ApproximationError We first analyze the impact of ALPAPPROX (and by the same argument, ALP-SEARCH with tolerance ε) failing to detect a violated constraint by comparing solution quality with that of exact ALP. All proofs are provided in an extended version of the paper. 9

Suppose ALP-APPROX terminates s.t. any missing constraint has violation of at most ϵ. We can show that: (a) the approximate VF produced by ALP-APPROX is no more than ϵ 1-γ away (in max-norm) from a feasible solution to (exact) ALP, i.e., it provides an upper bound on the ALP solution; and (b) the difference in our VF approximation (w.r.t. weighted 1-norm [de Farias and Van Roy, 2003]) is no more than ϵ 1-γ . This holds since any infeasible ALP solution can be made feasible by increasing the bias weight. A bound on value loss of the induced policy is obtainable using methods of [de Farias and Van Roy, 2003].

We can determine how well the MDP induced by PWC discretization matches the true logistic MDP; i.e., how different the optimal VFs for the MDPs are when using the true and approximated dynamics, respectively. To obtain meaningful bounds, we assume that for any given policy π, the Markov process induced by applying π mixes with rate µ. 10 The maximum difference in VFs obeys:

where LRE, the log relative error, is defined as LRE(̂ σ) = ln supf max [ ̂ σ(f ) σ(f) , 1-̂ σ(f ) 1-σ(f ) ], and ̂ σ is the PWC sigmoid approximation. Finally, we note that given a fixed discretization [δ0, . . . , δk] of f-space, the optimal choice of constants minimizing LRE within an interval is ̂ σ(f) = ln exp(δi+δi+1)+exp(δi+1) 1+exp(δi) , for δi ≤ f ≤ δi+1. Moreover, a PWC approximation to the sigmoid achieving LRE of at most ϵ can be constructed with O( 1ϵ ||u||1) intervals (see the extended paper for further details and proofs).

8 If a constraint is missed in I during a round of CG, a violated constraint may still be found in I later (if CG continues), since the subproblem changes with each master iteration.

9 Available at research.google.com/pubs/CraigBoutilier.html.

10 See [Boyen and Koller, 1998] for the mixing concept used here; it has the desirable property that it can be bounded using the structure of the DBN.

5 Empirical Results

We test the logistic MDP framework and the ALP-APPROX algorithm using models of various sizes derived from a targeted advertising domain. We generate logistic pCTR models that predict the probability of a user response ϕ, representing a click on a displayed (in-app) ad. pCTR models of several sizes are learned from data drawn over a period of one day with roughly 300M training examples. Each example has roughly 50 input random variables (with highly variable domain sizes), reflecting static user features, summaries of past behavior, ad characteristics, etc.

From these models, we construct a logistic MDP with a single binary response variable ϕ at the core of the logistic transition model. The transition functions are derived from the semantics of the features themselves. The reward function is 1 for a click, and our sequential objective is to maximize the expected discounted cumulative click-through rate. 11

We produce four models:

• TINY has two (natural) state variables (with domain sizes 6 and 42) and one action variable (domain size 7), giving rise to a one-hot encoding with 55 sparse binarized features (sbfs), of which 48 are state and 7 are action features. The induced state and action spaces have size 252 and 7, respectively.
• SMALL has: 6 state variables, 4 action variables; 86 sbfs (71 state, 15 action); 158,760 states, 126 actions.
• MEDIUM has: 11 state variables, 8 action variables; 421 sbfs (251 state, 170 action); approximately 243 states, 220M actions.
• LARGE has: 12 state variables, 11 action variables; 2854 sbfs (2630 state, 224 action); approximately 254 states, 239 actions.

We run ALP-APPROX using one basis function per sbf (e.g., LARGE uses 2854 basis functions). We use GLOP 12 to solve the master LP, and SCIP 13 for the Boolean subproblems. We solve the subproblems using various numbers of subintervals, or bands, to assess the impact of coarse vs. fine discretization.

Fig. 4 shows, for TINY, SMALL and MEDIUM, how objective value improves (for both 25 and 100 bands) and maximum constraint violation (MVC) decreases (both estimated and true constraints at 100 bands) with CG iteration. In each case, ALP-APPROX converges very quickly given the number of potential constraints. We see little difference in objective performance between 25 and 100 bands: 100 converges to slightly higher values. Other results (not shown)

11 Including bid predictions in the model to optimize for social welfare or revenue is straightforward, as would be including other reward factors of interest, if contained within the features.

12 See https://developers.google.com/optimization/.

13 See http://scip.zib.de/.

provide no appreciable improvement with up to 400 bands (w.r.t. 100), and 50 bands seems to be the "sweet spot" for this domain. For TINY we computed the exact ALP solution (no sigmoid approximation) using CG: our approximation was within 99.96% of the exact solution with 100 bands (and 97.3% with 25 bands). For SMALL, exact CG was not feasible, but we used early termination to obtain a loose upper bound on the exact solution: our approximation (100 bands) was within 94.3% of the "exact" upper bound. (Exact solutions are not feasible for larger instances.)

Fig. 5 shows (non-distributed) computation time per iteration for MEDIUM (trends are similar in the other instances). Total time for 400 iterations with 25 bands is roughly 600s.: a distributed implementation would take roughly 24s. (since solution time is dominated by the subproblem BOPs).

Fig. 6 shows the metrics above for LARGE, using 50 bands and 3000 CG iterations. It has a similar anytime profile w.r.t. objective value as the smaller problems. Despite the tremendous size of this discrete MDP, a distributed implementation would complete 3000 iterations in an estimated 19 minutes.

Finally, we perform a simple empirical comparison of the cumulative reward generated by the MDP-optimized policy to that obtained using myopic optimization. Using the MEDIUM domain, we generate trials by sampling 50 random ads from the data set as the eligible action set, 14 a random initial state from the data set, and then measure reward accrued over trajectories of length 60 by the myopic and ALP policies. We sample 40 eligible sets and 2500 initial states for each set, giving 100K trials. The ALP policy shows a small improvement of about 0.52% in value over the myopic policy. 15

6 Conclusion and FutureWork

We have proposed logistic MDPs as a model for sequential user interaction and developed approximate solution techniques based on ALP that handle the complexity introduced by logistic response variables. An attractive feature of Logistic MDPs is their exploitation of existing myopic response models and their features (the same applies to model-free RL), and our ALP method handles large problems but seems to approximate exact ALP very well.

14 This reflects the fact that for any impression only a small set of ads are considered eligible for various reasons (e.g., targeting, budget throttling, campaign expiration, etc.).

15 The feature subset used in this synthetic model gives a model with low pCTR and very limited user state, hence a small influence of actions on user state. Mean reward per trajectory: myopic: 0.75325; ALP: 0.75718; we did not find this difference to be statistically significant.

We are exploring several extensions of our model (several of these extensions are described in the full paper). Multiple response variables are easily modeled in logistic MDPs, though they complicate the ALP method. Crosses of features are often used in logistic regression to handle nonlinearities, and are easily incorporated into ALP). More complex response models like deep neural networks can also be incorporated into logistic MDPs, and certain DNNs can be linearized to allow our ALP methods to be used. 16 We are also exploring the adaptation of these methods to nonlinear VF approximators. Finally, the idea of compiling LP constraints into a compact form [Guestrin et al., 2003; Robbel et al., 2016] rather than relying on constraint generation is an intriguing prospect.

16 Thanks to Ross Anderson for conversations on this topic.