Analysis and Design of Thompson Sampling
for Stochastic Partial Monitoring

Partial monitoring (PM) is a general sequential decision-making problem with limited feedback (Rustichini, 1999; Piccolboni and Schindelhauer, 2001). PM is attracting broad interest because it includes a wide range of problems such as the multi-armed bandit problem (Lai and Robbins, 1985), a linear optimization problem with full or bandit feedback (Zinkevich, 2003; Dani et al., 2008), dynamic pricing (Kleinberg and Leighton, 2003), and label efficient prediction (Cesa-Bianchi et al., 2005).

A PM game can be seen as a sequential game that is played by two players: a learner and an opponent. At every round, the learner chooses an action, while the opponent chooses an outcome. Then, the learner suffers an unobserved loss and receives a feedback symbol, both of which are determined from the selected action and outcome. The main characteristic of this game is that the learner cannot directly observe the outcome and loss. The goal of the learner is to minimize his/her cumulative loss over all rounds. The performance of the learner is evaluated by the regret, which is defined as the difference between the cumulative losses of the learner and the optimal action (i.e., the action whose expected loss is the smallest).

There are mainly two types of PM games, which are the stochastic and adversarial settings (Piccolboni and Schindelhauer, 2001; Bartók et al., 2011). In the stochastic setting, the outcome at each round is determined from the opponent’s strategy, which is a probability vector over the opponent’s possible choices. On the other hand, in the adversarial setting, the outcomes are arbitrarily decided by the opponent. We refer to the PM game with finite actions and finite outcomes as a finite PM game. In this paper, we focus on the stochastic finite game.

One of the first algorithms for PM was considered by Piccolboni and Schindelhauer (2001). They proposed the FeedExp3 algorithm, the key idea of which is to use an unbiased estimator of the losses. They showed that the FeedExp3 algorithm attains $\operatorname{\tilde{O}}(T^{3/4})$ minimax regret for a certain class of PM games, and showed that any algorithm suffers linear minimax regret $\Omega(T)$ for the other class. Here $T$ is the time horizon and the notation $\operatorname{\tilde{O}}(\cdot)$ hides polylogarithmic factors. The upper bound $\operatorname{\tilde{O}}(T^{3/4})$ is later improved by Cesa-Bianchi et al. (2006) to $\operatorname{O}(T^{2/3})$, and they also provided a game with a matching lower bound.

In the seminal paper by Bartók et al. (2011), they classified PM games into four classes based on their minimax regrets. To be more specific, they classified games into trivial, easy, hard, and hopeless games, where their minimax regrets are $0$, $\operatorname{\tilde{\Theta}}(\sqrt{T})$, $\Theta(T^{2/3})$, and $\Theta(T)$, respectively. Note that the easy game is also called a locally observable game. After their work, several algorithms have been proposed for the finite PM problem (Bartók et al., 2012; Vanchinathan et al., 2014; Komiyama et al., 2015). For the problem-dependent regret analysis, Komiyama et al. (2015) proposed an algorithm that achieves $\operatorname{O}(\log T)$ regret with the optimal constant factor. However, it requires to solve a time-consuming optimization problem with infinitely many constraints at each round. In addition, this algorithm relies on the forced exploration to achieve the optimality, which makes the empirical performance near-optimal only after prohibitively many rounds, say, $10^{5}$ or $10^{6}$.

Thompson sampling (TS, Thompson, 1933) is one of the most promising algorithms on a variety of online decision-making problems such as the multi-armed bandit (Lai and Robbins, 1985) and the linear bandit (Agrawal and Goyal, 2013b), and the effectiveness of TS has been investigated both empirically (Chapelle and Li, 2011) and theoretically (Kaufmann et al., 2012; Agrawal and Goyal, 2013a; Honda and Takemura, 2014). In the literature on PM, Vanchinathan et al. (2014) proposed a TS-based algorithm called BPM-TS (Bayes-update for PM based on TS) for stochastic PM, which empirically achieved state-of-the-art performance. Their algorithm uses Gaussian approximation to handle the complicated posterior distribution of the opponent’s strategy. However, this approximation is somewhat heuristic and can degrade the empirical performance due to the discrepancy from the exact posterior distribution. Furthermore, no theoretical guarantee is provided for BPM-TS.

Our goals are to establish a new TS-based algorithm for stochastic PM, which allows us to sample the opponent’s strategy parameter from the exact posterior distribution, and investigate whether the TS-based algorithm can achive sub-linear regret in stochastic PM. Using the accept-reject sampling, we propose a new TS-based algorithm for PM (TSPM), which is equipped with a numerical scheme to obtain a posterior sample from the complicated posterior distribution. We derive a logarithmic regret upper bound $\operatorname{O}(\log{T})$ for the proposed algorithm on the locally observable game under a linearized variant of the problem. This is the first regret bound for TS on the locally observable game. Moreover, our setting includes the linear bandit problem and our result is also the first logarithmic expected regret bound of TS for the linear bandit, whereas a high-probability bound was provided, for example, in Agrawal and Goyal (2013b). Finally, we compare the performance of TSPM with existing algorithms in numerical experiments, and show that TSPM outperforms existing algorithms.

This paper studies finite stochastic PM games (Bartók et al., 2011). A PM game with $N$ actions and $M$ outcomes is defined by a pair of a loss matrix $\mathbf{L}=(\ell_{i,j})\in\mathbb{R}^{N\times M}$ and feedback matrix $\mathbf{H}=(h_{i,j})\in[A]^{N\times M}$, where $A$ is the number of feedback symbols and $[A]={\left\{1,2,\ldots,A\right\}}$.

A PM game can be seen as a sequential game that is played by two players: the learner and the opponent. At each round $t=1,2,\dots,T$, the learner selects action $i(t)\in[N]$, and at the same time the opponent selects an outcome based on the opponent’s strategy $p^{*}\in\mathcal{P}_{M}$, where $\mathcal{P}_{n}={\left\{p\in\mathbb{R}^{n}:p_{k}\geq 0,\sum_{k=1}^{n}p_{k}=1\right\}}$ is the $(n-1)$-dimensional probability simplex. The outcome $j(t)$ of each round is an independent and identically distributed sample from $p^{*}$, and then, the learner suffers loss $\ell_{i(t),j(t)}$ at time $t$. The learner cannot directly observe the value of this loss, but instead observes the feedback symbol $y(t)=h_{i(t),j(t)}\in[A]$. The setting explained above has been widely studied in the literature of stochastic PM (Bartók et al., 2011; Komiyama et al., 2015), and we call this the discrete setting. In Section 4, we also introduce a linear setting for theoretical analysis, which is a slightly different setting from the discrete one.

The learner aims to minimize the cumulative loss over $T$ rounds. The expected loss of action $i$ is given by $L_{i}^{\top}p^{*}$, where $L_{i}$ is the $i$-th column of $\mathbf{L}^{\top}$. We say action $i$ is optimal under strategy $p^{*}$ if $(L_{i}-L_{j})^{\top}p^{*}\leq 0$ for any $j\neq i$. We assume that the optimal action is unique, and without loss of generality that the optimal action is action $1$. Let $\Delta_{i}=(L_{i}-L_{1})^{\top}p^{*}\geq 0$ for $i\in[N]$ and $N_{i}(t)$ be the number of times action $i$ is selected before the $t$-th round. When the time step is clear from the context, we use $n_{i}$ instead of $N_{i}(t)$. We adopt the pseudo-regret to measure the performance: $\mathrm{Reg}(T)=\sum_{t=1}^{T}\Delta_{i(t)}=\sum_{i\in[N]}\Delta_{i}N_{i}(T+1)$. This is the relative performance of the algorithm against the oracle, which knows the optimal action $1$ before the game starts.

We introduce the following definitions to clarify the class of PM games, for which we develop an algorithm and derive a regret upper bound. The following cell decomposition is the concept to divide the simplex $\mathcal{P}_{M}$ based on the loss matrix to identify the optimal action, which depends on the opponent’s strategy $p^{*}$.

Each cell is a convex closed polytope. Next, we define neighbors between two Pareto-optimal actions, which intuitively means that the two actions “touch” each other in their surfaces.

Note that the neighborhood action set $N_{{i},{j}}^{+}$ includes actions $i$ and $j$ from its definition. Next, we define the signal matrix, which encodes the information of the feedback matrix $\mathbf{H}$ so that we can utilize the feedback information.

Note that if we define the signal matrix as above, $S_{i}p^{*}\in\mathbb{R}^{A}$ is a probability vector over feedback symbols of action $i$. The following local observability condition separates easy and hard games, this condition intuitively means that the information obtained by taking actions in the neighborhood action set $N_{{i},{j}}^{+}$ is sufficient to distinguish the loss difference between actions $i$ and $j$.

We also consider the concept of the strong local observability condition, which implies the above local observability condition.

This condition was assumed in the theoretical analysis in Vanchinathan et al. (2014), and we also assume this condition in theoretical analysis in Section 4. Note that the strong local observability means that, for any $j\neq k$, there exists $z_{j,k}\neq 0\in\mathbb{R}^{2A}$ such that $L_{j}-L_{k}=(S_{j}^{\top},S_{k}^{\top})\,z_{j,k}$.

Although BPM-TS is one of the best methods for stochastic PM, it approximates the posterior by a Gaussian distribution in a heuristic way, which can degrade the empirical performance due to the distributional discrepancy from the exact posterior distribution. Furthermore, no theoretical guarantee is provided for BPM-TS. In this paper, we mitigate these problems by providing a new algorithm for stochastic PM, which allows us to exactly draw samples from the posterior distribution. We also give theoretical analysis for the proposed algorithm.

In this section, we present a new algorithm for stochastic PM games, where we name the algorithm TSPM (TS-based algorithm for PM). The algorithm is given in Algorithm 1, and we will explain the subroutines in the following.

This section considers a regret upper bound of the TSPM algorithm.

In the theoretical analysis, we consider a linear setting of PM. In the linear PM, the learner suffers the expected loss $L_{i(t)}^{\top}p^{*}$ as in the discrete setting, and receives feedback vector $y(t)=S_{i}p^{*}+\epsilon_{t}$ for $\epsilon_{t}\sim\mathcal{N}(0,I_{M})$ whereas the one-hot representation of $y(t)$ is distributed by the probability vector $S_{i}p^{*}$ in the discrete setting. Therefore, if $\epsilon_{t}$ can be regarded as a sub-Gaussian random variable as in Kirschner et al. (2020) then the linear PM includes the discrete PM, though our theoretical analysis requires $\epsilon_{t}$ to be Gaussian. The relation between discrete and linear settings can also be seen from the observation that bandit problems with Bernoulli and Gaussian rewards can be expressed as discrete and linear PM, respectively. The linear PM also includes the linear bandit problem, where the feedback vector is expressed as $L_{i}^{\top}p^{*}+\epsilon_{t}$.

In the linear PM, $G_{t}(p)$ in (2) becomes the exact posterior distribution rather than a proposal distribution. The definition of the cell decomposition for this setting is largely the same as that of discrete setting and detailed in Appendix F. Therefore, TS with exact posterior sampling in the linear PM corresponds to TSPM-Gaussian. In the linear PM, the unknown parameter $p^{*}$ is in $\mathbb{R}^{M}$ rather than in $\mathcal{P}_{M}$, and therefore we consider the prior $\pi{\left(p\right)}=\mathcal{N}(0,\lambda I_{M})$ over $\mathbb{R}^{M}$, where the posterior distribution becomes $\mathcal{N}(B_{t}^{-1}b_{t},\,B_{t}^{-1})$.

There are a few works that analyze TS for the PM because of its difficulty. For example in Vanchinathan et al. (2014), an analysis of the TS-based algorithm (BPM-TS) is not given despite the fact that its performance is better than the algorithm based on a confidence ellipsoid (BPM-LEAST). Zimmert and Lattimore (2019) considered the theoretical aspect of a variant of TS for the linear PM in view of the Bayes regret, but this algorithm is based on the knowledge on the time horizon and different from the family of TS used in practice. More specifically, their algorithm considers the posterior distribution for regret (not pseudo-regret), and an action is chosen according to the posterior probability that each arm minimizes the cumulative regret. Thus, the time horizon also needs to be known.

In this section, we numerically compare the performance of TSPM and TSPM-Gaussian against existing methods, which are RandomPM (the algorithm which selects action randomly), FeedExp3 (Piccolboni and Schindelhauer, 2001), and BPM-TS (Vanchinathan et al., 2014). Recently, Lattimore and Szepesvári (2019) considered the sampling-based algorithm called Mario sampling for easy games. Mario sampling coincides with TS (except for the difference between pseudo-regret and regret with known time horizon) mentioned in the last section when any pair of actions is a neighbor. As shown in Appendix G, this property is indeed satisfied for dp-easy games defined in the following. Therefore, the performance is essentially the same between TSPM with $R=1$ and Mario sampling. To compare the performance, we consider a dynamic pricing problem, which is a typical example of PM games. We conducted experiments on the discrete setting because the experiments for PM has been mainly focused on the discrete setting.

In the dynamic pricing game, the player corresponds to a seller, and the opponent corresponds to a buyer. At each round, the seller sells an item for a specific price $i(t)$, and the buyer comes with an evaluation price $j(t)$ for the item, where the selling price and the evaluation price correspond to the action and outcome, respectively. The buyer buys the item if the selling price $i(t)$ is smaller than or equal to $j(t)$ and not otherwise. The seller can only know if the buyer bought the item (denoted as feedback $0$) or did not buy the item (denoted as $1$). The seller aims to minimize the cumulative “loss”, and there are two types of definitions for the loss, where each induced game falls into the easy and hard games. We call them dp-easy and dp-hard games, respectively.

In both cases, the seller incurs the constant loss $c>0$ when the item is not bought due to the loss of opportunity to sell the item. In contrast, when the item is not bought, the loss incurred to the seller is different between these settings. The seller in the dp-easy game does not take the buyer’s evaluation price into account. In other words, the seller gains the selling price $i(t)$ as a reward (equivalently incurs $-i(t)$ as a loss). Therefore, the loss for the selling price $i(t)$ and the evaluation $j(t)$ is

This setting can be regarded as a generalized version of the online posted price mechanism, which was addressed in, e.g.,  Blum et al. (2004) and Cesa-Bianchi et al. (2006), and an example of strongly locally observable games.

On the other hand, the seller in dp-hard game does take the buyer’s evaluation price into account when the item is bought. In other words, the seller incurs the difference between the opponent evaluation and the selling price $j(t)-i(t)$ as a loss because the seller could have made more profit if the seller had sold at the price $j(t)$. Therefore, the loss incurred at time $t$ is

This setting is also addressed in Cesa-Bianchi et al. (2006), and belongs to the class of hard games. Note that our algorithm can also be applied to a hard game, though there is no theoretical guarantee.

Figure 2 shows the number of rejections at each time step in the accept-reject sampling. We counted the number of times that either Line 2 in Algorithm 2 or Line 3 in Algorithm 3 was not satisfied. In the accept-reject sampling, it is desirable that the frequency of rejection does not increase as the time-step $t$ and does not increase rapidly with the number of outcomes. We can see that the former one is indeed satisfied. For the latter property, the frequency of rejection becomes unfortunately large when exact sampling ($R=1$) is conducted. Still, we can substantially improve this frequency by setting $R$ to be a small value or zero, which still keeps regret tremendously better than that of BPM with almost the same time-efficiency as BPM-TS.

This paper investigated Thompson sampling (TS) for stochastic partial monitoring from the algorithmic and theoretical viewpoints. We provided a new algorithm that enables exact sampling from the posterior distribution, and numerically showed that the proposed algorithm outperforms existing methods. Besides, we provided an upper bound for the problem-dependent logarithmic expected pseudo-regret for the linearized version of the partial monitoring. To our knowledge, this bound is the first logarithmic problem-dependent expected pseudo-regret bound of a TS-based algorithm for linear bandit problems and strongly locally observable partial monitoring games.

There are several remaining questions. As mentioned in Section 4, Kirschner et al. (2020) considered linear partial monitoring with the feedback structure $y(t)=S_{i(t)}p^{*}+\epsilon_{t}$, where $(\epsilon_{t})_{t=1}^{T}$ is a sequence of independent sub-Gaussian noise vector in $\mathbb{R}^{M}$. This setting is the generalization of our linear setting, where $(\epsilon_{t})_{t=1}^{T}$ are i.i.d. Gaussian vectors. Therefore, a natural question that arises is whether we can extend our analysis on TSPM-Gaussian to the sub-Gaussian case, although we believe it would be not straightforward as discussed in Section 4. It is also an important open problem to derive a regret bound on TSPM using the exact posterior sampling for the discrete partial monitoring. Although we conjecture that the algorithm also achieves logarithmic regret for the setting, there still remain some difficulties in the analysis. In particular, we have to handle the KL divergence in $f_{t}(p)$ and consider the restriction of the support of the opponent’s strategy to $\mathcal{P}_{M}$, which make the analysis much more complicated. Besides, it is worth noting that the theoretical analysis of TS for hard games has never been theoretically investigated. We believe that in general TS suffers linear regret in the minimax sense due to its greediness. However, we conjecture that TS can achieve the sub-linear regret for some specific instances of hard games in the sense of the problem-dependent regret, as empirically observed in the experiments. Finally, it is an important open problem to derive the minimax regret for anytime TS-based algorithms. This needs more detailed analysis on $\operatorname{o}(\log T)$ terms in the regret bound, which were dropped in our main result.

The authors would like to thank the meta-reviewer and reviewers for a lot of helpful comments. The authors would like to thank Kento Nozawa and Ikko Yamane for maintaining servers for our experiments, and Kenny Song for helpful discussion on the writing. TT was supported by Toyota-Dwango AI Scholarship, and RIKEN Junior Research Associate Program for the final part of the project. JH was supported by KAKENHI 18K17998, and MS was supported by KAKENHI 17H00757.