Overview#

• Advantage: It is both scalable and robust. Furthermore, it also accounts for the iter-item heterogeneity.

• Disadvantage:

• Application Situation: Useful when presenting a ranked list of items, with only one selected at each interaction. The outcome is binary. Static feature information.

Main Idea#

MTSS_Cascade is an example of the general Thompson Sampling(TS)-based framework, MTSS [1], to deal with online learning to rank problems.

Review of MTSS: MTSS[1] is a meta-learning framework designed for large-scale structured bandit problems [2]. Mainly, it is a TS-based algorithm that learns the information-sharing structure while minimizing the cumulative regrets. Adapting the TS framework to a problem-specific Bayesian hierarchical model, MTSS simultaneously enables information sharing among items via their features and models the inter-item heterogeneity. Specifically, it assumes that the item-specific parameter ${\theta }_i=E[W_t(i)]$ is sampled from a distribution $g({\theta }_i|{\mathit{s}}_i,\mathit{\gamma })$ instead of being entirely determined by ${\mathit{s}}_i$ via a deterministic function. Here, $g$ is a model parameterized by an unknown vector $\mathit{\gamma }$. The following is the general feature-based hierarchical model MTSS considered.

where $Q(\mathit{\gamma })$ is the prior distribution for $\mathit{\gamma }$. Overall, MTTS is a general framework that subsumes a wide class of practical problems, scalable to large systems, and robust to the specification of the generalization model.

Review of MTSS_Cascade: To characterize the relationship between items using their features, one example choice of $g$ is the popular Beta-Bernoulli logistic model [1,2], where ${\theta }_i\sim Beta(logistic({\mathit{s}}_i^T\mathit{\gamma }),\varphi )$ for some known parameter $\varphi$. We adopt the mean-precision parameterization of the Beta distribution, with $logistic({\mathit{s}}_i^T\mathit{\gamma })$ being the mean and $\varphi$ being the precision parameter. Specifically, the full model is as follows:

The prior $Q(\mathit{\gamma })$ can be chosen as many appropriate distributions. For instance, we choose the prior $\mathit{\gamma }\sim \mathcal{N}({\mathit{\mu }}_{\mathit{\gamma }},{\mathbf{\Sigma }}_{\mathit{\gamma }})$ with parameters as known. To update the posterior of $\mathit{\gamma }$, we utilize the Pymc3 package [3]. With a given $\mathit{\gamma }$, the posterior of $\mathit{\theta }$ enjoys the Beta-Geometric conjugate relationship and hence can be updated explicitly and efficiently. Finally, for each round, we select the top $K$ items with the highest estimated attractiveness factors. It should be noted that the posterior updating step differs for different pairs of the $Q(\mathit{\gamma })$ and the reward distribution, and the corresponding code can be easily modified to different prior/reward distribution specifications if necessary.

Algorithm Details#

At each round $t$, given the feedback ${\mathcal{H}}_t$ received from previous rounds, there are two major steps including posterior sampling and combinatorial optimization. Specifically, the posterior sampling step is decomposed into four steps: 1. approximating a posterior distribution of $\mathit{\gamma }$, $P(\mathit{\gamma }|{\mathcal{H}}_t)$, by Pymc3; 2. sampling a $\tilde{\mathit{\gamma }}$ from $P(\mathit{\gamma }|{\mathcal{H}}_t)$; 3. updating the posterior distribution of $\mathit{\theta }$ conditional on $\tilde{\mathit{\gamma }}$, $P(\mathit{\theta }|\tilde{\mathit{\gamma }},{\mathcal{H}}_t)$, which has an explicit form under the assumption of a Beta-Bernoulli logistic model; 4. sampling $\tilde{\mathit{\theta }}$ from $P(\mathit{\theta }|\tilde{\mathit{\gamma }},{\mathcal{H}}_t)$. Then, the action $A_t$ is selected greedily as $A_t=argma{x}_{a\in \mathcal{A}}E(R_t(a)\mid \tilde{\mathit{\theta }})$. Specifically, the top $K$ items with the highest ${\tilde{\theta }}_i$ will be displayed. Note that $\tilde{\mathit{\gamma }}$ can be sampled in a batch mode to further facilitate computationally efficient online deployment.

Key Steps#

For round $t=1,2,\cdots$:

1. Approximate $P(\mathit{\gamma }|{\mathcal{H}}_t)$ by Pymc3;

2. Sample $\tilde{\mathit{\gamma }}\sim P(\mathit{\gamma }|{\mathcal{H}}_t)$;

3. Update $P(\mathit{\theta }|\tilde{\mathit{\gamma }},{\mathcal{H}}_t)$;

4. Sample $\tilde{\mathit{\theta }}\sim P(\mathit{\theta }|\tilde{\mathit{\gamma }},{\mathcal{H}}_t)$;

5. Take the action $A_t$ w.r.t $\tilde{\mathit{\theta }}$ such that $A_t=argma{x}_{a\in \mathcal{A}}E(R_t(a)\mid \tilde{\mathit{\theta }})$;

6. Receive reward $R_t$.

*Notations can be found in either the inroduction of the chapter “Structured Bandits” or the introduction of the cascading Bandit problems.

Demo Code#

import numpy as np
from causaldm.learners.CPL4.Structured_Bandits.Cascade import MTSS_Cascade

WARNING (theano.tensor.blas): Using NumPy C-API based implementation for BLAS functions.

from causaldm.learners.CPL4.Structured_Bandits.Cascade import _env_realCascade as _env
env = _env.Cascading_env(K = 3, seed = 0)

phi_beta = 1/4
K = env.K
S = env.Phi
gamma_prior_mean = np.zeros(env.p)
gamma_prior_cov = np.identity(env.p)
update_freq = 10
n_init = 1000
seed = 0
MTSS_agent = MTSS_Cascade.MTSS_Cascade(phi_beta = phi_beta, K = K, Xs = S, 
                                       gamma_prior_mean = gamma_prior_mean, gamma_prior_cov = gamma_prior_cov,
                                       update_freq = update_freq, n_init = n_init, seed = seed)

t = 0
A = MTSS_agent.take_action(S)
W, E, R = env.get_reward(A)
MTSS_agent.receive_reward(A, W, E, t, S)
A, W, E, R

(array([2189, 1610, 1206], dtype=int64),
 array([0., 0., 0.]),
 array([1., 1., 1.]),
 0.0)

References#

[1] Wan, R., Ge, L., & Song, R. (2022). Towards Scalable and Robust Structured Bandits: A Meta-Learning Framework. arXiv preprint arXiv:2202.13227.

[2] Forcina, A. and Franconi, L. Regression analysis with the beta-binomial distribution. Rivista di Statistica Applicata, 21(1), 1988.

[3] Salvatier J., Wiecki T.V., Fonnesbeck C. (2016) Probabilistic programming in Python using PyMC3. PeerJ Computer Science 2:e55 DOI: 10.7717/peerj-cs.55.