From Predictions to Decisions:
The Importance of Joint Predictive Distributions

Consider a sequence of pairs $((X_{t},Y_{t+1}):t=0,1,2,\ldots)$, where each $X_{t}$ is a feature vector and each $Y_{t+1}$ is its target label. Feature vectors $(X_{t}:t=0,1,2,\ldots)$ are i.i.d. according to an input distribution $P_{X}$. Each target label $Y_{t+1}$ is independent of all other data, conditioned on $X_{t}$, and distributed according to $\mathcal{E}(\cdot|X_{t})$. The conditional distribution $\mathcal{E}$ is referred to as the environment. The environment $\mathcal{E}$ is random; and this reflects the agent’s uncertainty about how labels are generated given features. Note that $\mathds{P}(Y_{t+1}\in\cdot|\mathcal{E},X_{t})=\mathcal{E}(\cdot|X_{t})$ and $\mathds{P}(Y_{t+1}\in\cdot|X_{t})=\mathbb{E}[\mathcal{E}(\cdot|X_{t})|X_{t}]$.

In supervised learning, we consider an agent that learns about the environment $\mathcal{E}$ from a training dataset

and aims to predict the target labels

at $\tau$ feature vectors $X_{T:T+\tau-1}\equiv(X_{T},\dots,X_{T+\tau-1})$.

Conditioned on the environment $\mathcal{E}$, a predictive distribution over the target labels is given by

Conditioned instead on the training data, the predictive distribution becomes

In a sense, $\overline{P}_{T+1:T+\tau}$ represents the result of perfect inference. Since the associated computations are intractable for environments of interest, we instead consider agents that approximate this predictive distribution. Specifically, we consider agents that represent the approximation in terms of a generative model. The agent’s predictions are parameterized by a vector $\theta_{T}$ that the agent learns from the training data $\mathcal{D}_{T}$. The vector $\theta_{T}$ is conditionally independent of $\mathcal{E}$ conditioned on $\mathcal{D}_{T}$. For any inputs $X_{T:T+\tau-1}$, $\theta_{T}$ determines a predictive distribution, which could be used to sample imagined outcomes $\hat{Y}_{T+1:T+\tau}$. Hence, the agent’s $\tau^{\rm th}$-order predictive distribution is given by

When $\tau=1$, we alternatively use $\hat{P}_{T+1}$, $\overline{P}_{T+1}$, and $P^{*}_{T+1}$ to denote $\hat{P}_{T+1:T+\tau}$, $\overline{P}_{T+1:T+\tau}$, and $P^{*}_{T+1:T+\tau}$, respectively.

Note that if $\tau=1$, $\hat{P}_{T+1}$ represents a marginal prediction: it predicts the label $Y_{T+1}$ for a single input $X_{T}$. On the other hand, for $\tau>1$, it represents a joint prediction over labels at $\tau$ input features.

Before proceeding, we use a simple coin flipping example to illustrate that evaluating marginal and joint predictive distributions can result in very different answers. Suppose that $(Y_{t+1}:t=0,1,\ldots)$ are generated by repeated tosses of a possibly biased coin with unknown probability $p$ of heads, with $Y_{t+1}=1$ and $Y_{t+1}=0$ indicating heads and tails, respectively. Consider two agents with different beliefs: Agent 1 assumes $p=2/3$ and models the outcome of each coin toss as independent conditioned on $p$. Agent 2 assumes that $p=1$ with probability $2/3$ and $p=0$ with probability $1/3$; that is, the coin either produces only heads or only tails. Let $\hat{Y}^{1}_{t+1}$ and $\hat{Y}^{2}_{t+1}$ denote the outcomes imagined by the two agents. Despite their differing assumptions, the two agents generate identical marginal predictive distributions: $\mathds{P}(\hat{Y}^{1}_{t+1}=0)=\mathds{P}(\hat{Y}^{2}_{t+1}=0)=1/3$.

On the other hand, the joint predictions of these two agents differ for $\tau>1$:

Evaluating marginal predictions cannot distinguish between the two agents, though for a specific prior distribution over $p$, one agent could be right and the other wrong. One must evaluate joint predictions to make this distinction.

Cross-entropy loss is perhaps the most widely used metric in machine learning, though it is typically only used to evaluate marginal predictive distributions. For our supervised learning formulation, an agent’s marginal cross-entropy loss takes the form

where the expectation is over both $\hat{P}_{T+1}$ and $Y_{T+1}$, and the superscript “$1$” in $\mathbf{d}_{\mathrm{CE}}^{1}$ indicates that this evaluates marginal predictions. Note that the marginal distribution $\hat{P}_{T+1}$ is random because it depends on $\theta_{T}$ and $X_{T}$.

It is straightforward to extend the cross-entropy loss to assess joint predictive distributions. Generalizing Equation (1), for any $\tau=1,2,\ldots$, we define the $\tau^{\textrm{th}}$-order cross-entropy loss:

where the expectation is over $\hat{P}_{T+1:T+\tau}$ and $Y_{T+1:T+\tau}$. Note that the $\tau^{\textrm{th}}$-order joint distribution $\hat{P}_{T+1:T+\tau}$ is also random, since it depends on $\theta_{T}$ and $X_{T:T+\tau-1}$.

One can use the joint cross-entropy loss defined in Equation (2) to assess joint predictive distributions. However, it can be helpful to offset the metric by a baseline to convert it into the Kullback–Leibler (KL) divergence. We will take $\overline{P}_{T+1:T+\tau}$, which is the perfect posterior predictive, to be our baseline. As we will see, since $\overline{P}_{T+1:T+\tau}$ does not depend on the agent, our measure of KL-divergence and the cross-entropy loss are effectively equivalent in the sense that they only differ by a constant that does not depend on the agent. However, KL-divergence exhibits properties that allow for a more elegant mathematical analysis.

The $\tau^{\textrm{th}}$-order expected KL-divergence with respect to $\overline{P}$ is defined by

where the expectation is over the distributions $\overline{P}_{T+1:T+\tau}$ and $\hat{P}_{T+1:T+\tau}$, which depend in turn on the data $\mathcal{D}_{T}$, the agent parameters $\theta_{T}$, and the $\tau$ inputs $X_{T:T+\tau-1}$.

Note that KL-divergence is minimized when $\hat{P}_{T+1:T+\tau}=\overline{P}_{T+1:T+\tau}$, with the minimum being zero. Further, our two metrics are related according to

Since $\overline{P}_{T+1:T+\tau}(Y_{T+1:T+\tau})$ does not depend on the agent, our two metrics rank agents identically.

An unbiased estimate of cross-entropy loss can be computed based on a test data sample, according to

The same is not true for $\mathbf{d}_{\mathrm{KL}}^{\tau}$, which can only be estimated if also given an estimate of $\mathbb{E}[\log\overline{P}_{T+1:T+\tau}(Y_{T+1:T+\tau})]$. Hence, $\mathbf{d}_{\mathrm{KL}}^{\tau}$ serves only as conceptual tools in our analysis and not an evaluation metric that can be applied with empirical data. While it ranks agents identically with $\mathbf{d}_{\mathrm{CE}}^{\tau}$, $\mathbf{d}_{\mathrm{KL}}^{\tau}$ is more natural as a metric since its minimum is zero and it accommodates more elegant analysis.

Our $\mathbf{d}_{\mathrm{KL}}^{\tau}$ metric assesses error incurred by the predictive distribution $\hat{P}_{T+1:T+\tau}$. A common approach to generating such a predictive distribution is through estimating a posterior distribution over environments and using that posterior distribution to generate the predictive distribution. In such a context, $\theta_{T}$ parameterizes the estimated posterior distribution. Let $\hat{\mathcal{E}}$ be an imaginary environment sampled from this posterior distribution. To offer some intuition for $\mathbf{d}_{\mathrm{KL}}^{\tau}$, we consider in this section its relation to the KL-divergence between the distributions of the true and imaginary environments.

Let $\hat{Y}_{T+1:T+\tau}$ denote a sequence of imaginary outcomes, with each $\hat{Y}_{t+1}$ sampled independently from $\hat{\mathcal{E}}(\cdot|X_{t})$. If the support of the input distribution $P_{X}$ is exhaustive, the support of the imaginary environment distribution $\mathds{P}(\hat{\mathcal{E}}\in\cdot|\theta_{T})$ contains that of the true environment distribution $\mathds{P}(\mathcal{E}\in\cdot|\mathcal{D}_{T})$, and the environment distributions satisfy suitable regularity conditions, then

In other words, under certain technical conditions, as the number $\tau$ of test data pairs grows, $\mathbf{d}_{\mathrm{KL}}^{\tau}$ converges to the error in the estimated posterior distribution over environments, measured in terms of KL-divergence.

One might wonder why we should use $\mathbf{d}_{\mathrm{KL}}^{\tau}$ rather than the KL divergence between the true and imaginary environments

to evaluate the agents. There are several reasons for it. First, practical agent designs often do not satisfy the requisite regularity conditions, and hence (4) becomes infinite. For example, it is common to approximate the posterior distribution $\mathcal{E}$ using an ensemble of environment models (see, e.g., Lu & Van Roy (2017)). Such an ensemble represents a distribution with finite support though the posterior may have infinite support. On the other hand, for any finite $\tau$, $\mathbf{d}_{\mathrm{KL}}^{\tau}$ is finite. Second, $\mathbf{d}_{\mathrm{CE}}^{\tau}$, which is equivalent to $\mathbf{d}_{\mathrm{KL}}^{\tau}$ up to a constant, can be computed based on data, whereas computing (4) requires access to the posterior distribution of $\mathcal{E}$. Finally, as we will establish later, $\mathbf{d}_{\mathrm{KL}}^{\tau}$ with finite $\tau$ is sufficient to support effective decisions in downstream tasks such as multi-armed bandits.

We now show that, for any $\tau$, accuracy in terms of $\mathbf{d}_{\mathrm{KL}}^{\tau}$ is sufficient to guarantee an effective decision if the decision is judged in relation only to $Y_{T+1:T+\tau}$. In particular, suppose an action $a$ selected from a set $\mathcal{A}$ results in an expected reward

where $r$ is a reward function with range $[0,1]$. The following result bounds the loss in expected reward of a decision that is based on the estimate $\hat{P}_{T+1:T+\tau}$ instead of the posterior $\overline{P}_{T+1:T+\tau}$.

This results follows from Pinsker’s inequality and Jensen’s inequality. A proof is provided in Appendix A.

Proposition 2.1 ensures that if a decision maximizes an approximation to expected reward, with the expectation approximated using the predictive distribution $\hat{P}_{T+1:T+\tau}$, then the action will be within $\sqrt{2\mathbf{d}_{\mathrm{KL}}^{\tau}}$ of what is achievable given the posterior predictive distribution $\overline{P}_{T+1:T+\tau}$. In this sense, $\mathbf{d}_{\mathrm{KL}}^{\tau}$ is a universal evaluation metric: its value ensures a level of performance in any decision problem.

Consider a sequential decision problem with $K$ actions. The environment $\mathcal{E}$ prescribes observation probabilities. During each time step $t=0,1,2,\ldots$, the agent selects an action $A_{t}$ and observes an outcome $Y_{t+1}$ produced by the environment. Conditioned on the environment $\mathcal{E}$ and action $A_{t}$, the next observation $Y_{t+1}$ is sampled from $\mathcal{E}(\cdot|A_{t})$ independently across time. There is a real-valued reward function $r$ that encodes the agent’s preferences over outcomes. The objective of the agent is to optimize the expected return over some long horizon $T$,

where the expectation is taken over random outcomes, algorithmic randomness, and prior over $\mathcal{E}$.

We will now show that, even if an agent can make perfect predictions for the outcomes of each action, these marginal predictions per action can be insufficient to drive efficient exploration. The root cause is that, at any time step $t$, the rewards and observations at future time steps $t^{\prime}>t$ are coupled through the unknown environment $\mathcal{E}$. Clearly, we can imagine problem instances where one action reveals the full structure of the environment, but does not itself produce a reward. In this case, an agent that simply makes good marginal predictions on the reward of each action is clearly insufficient to take advantage of this informative action. However, perhaps more interestingly, this coupling can occur even when rewards evolve independently per action given the environment.

To make this point clear, we will consider an extension of the coin tossing example from Section 2.2. We consider an Bernoulli bandit with $K$ independent actions where the reward is simply taken to be the $Y_{t+1}$. For the first $K-1$ actions the agents knows that the outcome is distributed $\mathrm{Ber(0.5)}$, a pure 50% chance. However, the final action produces a deterministic outcome of either $1$ or $0$, but it is equally likely to be of either kind. Clearly, the optimal policy to maximize long term reward is to first select the final action to see if it is optimal and, based on that outcome, choose the arm that maximizes expected reward given full knowledge of $\mathcal{E}$ for all future steps. However, any agent that only matches marginal predictions cannot distinguish the final arm from any of the others. As such, it will be impossible for the agent to do better than random chance over the $K$ arms. On average, it will require $\Theta(K)$ time steps to identify the optimal policy.

Just as in the coin flip example, the difference between the informative and uninformative actions is fully revealed when we look at $\tau^{\textrm{th}}$-order predictive distributions for any $\tau>1$. In general, it is only through examining the evolution of future outcomes beyond myopic marginals that allows an agent to optimize the long term returns. In the next subsection, we will expand on this intuitive argument and relate the ability to predict future outcomes to agent performance. In fact, we will establish a bound on performance that guarantees that if you can make approximate predictions $O(K)$ steps into the future, then it will be sufficient to drive efficient exploration.

As explained in the previous subsection, in a sequential decision problem, it is in general desirable to consider uncertainties jointly across actions in order to make effective decisions. Thus, to simplify exposition, we consider predictions for a vector of outcomes, $\mathbf{Y}\in\Re^{K}$, with each entry corresponding to the outcome of an action. In this section, we will relate the quality of future predictions about $\mathbf{Y}$ to agent performance on a Bernoulli bandit with correlated arms.

Recall that in a $K$-armed Bernoulli bandit, the environment $\mathcal{E}$ is identified by parameters $p=(p_{1},\ldots,p_{K})$, where $p_{k}\in[0,1]$ is the expected reward of the $k^{\rm th}$ action. We make no assumptions about the prior $\mathds{P}(p\in\cdot)$. In particular, there could be dependencies, where an observed outcome from trying one action informs our beliefs about other actions. We define the history by time $t$ as $H_{t}=\left(A_{0},Y_{1},\ldots,A_{t-1},Y_{t}\right)$.

We use $\tilde{\mathbf{Y}}_{1:\tau}$ to denote a sequence of $\tau$ vectors sampled from the environment $\mathcal{E}$. Specifically, these $\tau$ vectors are conditionally independent given $\mathcal{E}$. Each vector has dimension $K$, and the $k^{\rm th}$ component of each vector is conditionally independently sampled from $\mathrm{Ber}(p_{k})$. On the other hand, consider an agent that can also generate a sequence of $K$-dimensional binary vectors at each time $t$. Let $\theta_{t}$ denote its parameters, and $\hat{\mathbf{Y}}^{t}_{1:\tau}$ denote a sequence of $\tau$ binary vectors sampled from it. In this subsection, we establish that if an agent can produce good $\tau^{\rm th}$-order predictive distributions in the sense that

for some small $\epsilon\geq 0$, then based on this agent one can design bandit algorithms that achieve near-optimal performance.

Specifically, we consider an approximate version of Thompson sampling algorithm, which is described in Algorithm 1. This algorithm proceeds as follows: at each time $t$, it first samples $\tau$ binary vectors $\hat{\mathbf{Y}}^{t}_{1:\tau}$ based on the agent predictive distribution; then, it samples a vector $\hat{p}^{t}\in[0,1]^{K}$ from the conditional distribution $\mathds{P}(p\in\cdot|\tilde{\mathbf{Y}}_{1:\tau}=\hat{\mathbf{Y}}^{t}_{1:\tau})$; finally, it chooses an action $A_{t}$ greedy to $\hat{p}^{t}$ and update the agent parameters based on new observations. Note that Algorithm 1 is general in the sense that it does not depend on the agent’s uncertainty representation. Instead, it only requires that the agent can simulate hypothetical observations, sampled from a joint predictive distribution. Also note that Algorithm 1 reduces to the standard (exact) Thompson sampling algorithm when $\mathds{P}(\hat{\mathbf{Y}}_{1:\tau}\in\cdot|\theta_{t})=\mathds{P}(\tilde{\mathbf{Y}}_{1:\tau}\in\cdot|H_{t})$ and $\tau\rightarrow\infty$. We use this algorithm to establish that an agent that performs well based on a particular loss function retains enough information to enable efficient exploration.²²2Note that $\min\operatorname*{arg\,max}_{k}\hat{p}^{t}_{k}$ is well defined. Specifically, $\operatorname*{arg\,max}_{k}\hat{p}^{t}_{k}\subseteq\{1,\ldots,K\}$ is a set.

As is standard in bandit literature, we measure the performance of Algorithm 1 using (Bayes) cumulative regret, which is defined as

where $A^{*}=\min\operatorname*{arg\,max}_{k}p_{k}$ is one optimal action. Similarly, the expectation is over random outcomes, algorithmic randomness, and prior over $\mathcal{E}$. We can establish the following regret bound for Algorithm 1:

We now briefly discuss the regret bound in Theorem 5.1. First, note that if an agent can make good predictions $\tau\geq K/\epsilon$ steps into the future, then this regret bound reduces to $O(\sqrt{KT\log(K)}+\sqrt{K\epsilon}T)$, which is sufficient to ensure efficient exploration. Second, notice that this regret bound consists of three terms. The linear regret term $\sqrt{2\epsilon}T$ is due to the expected KL-divergence loss of the agent. Specifically, if the agent makes a perfect prediction in the sense that $\mathds{P}(\hat{\mathbf{Y}}_{1:\tau}^{t}\in\cdot|\theta_{t})=\mathds{P}(\tilde{\mathbf{Y}}_{1:\tau}\in\cdot|H_{t})$ for all $t$, then this linear regret term will reduce to zero. On the other hand, another linear regret term $KT/\sqrt{2\tau}$ is due to the fact that we choose $\tilde{A}$ as the learning target, which can be a sub-optimal action. It is obvious that as $\tau\rightarrow\infty$, $\tilde{A}$ will converge to $A^{*}$ and this linear regret term will reduce to zero. Finally, the sublinear regret term $\sqrt{\frac{1}{2}KT\log K}$ is exactly the regret bound for the exact Thompson sampling algorithm (Russo & Van Roy, 2016). This is not surprising since when $\epsilon=0$ (i.e. $\mathds{P}(\hat{\mathbf{Y}}_{1:\tau}^{t}\in\cdot|\theta_{t})=\mathds{P}(\tilde{\mathbf{Y}}_{1:\tau}\in\cdot|H_{t})$) and $\tau\rightarrow\infty$, Algorithm 1 reduces to the exact Thompson sampling algorithm.

Finally, it is worth mentioning that we conjecture that we can develop results similar to Theorem 5.1 for more practical algorithms and more general sequential decision problems. Note that in Algorithm 1, sampling $\hat{p}^{t}$ from $\mathds{P}(p\in\cdot|\tilde{\mathbf{Y}}_{1:\tau}=\hat{\mathbf{Y}}^{t}_{1:\tau})$ can be computationally expensive. Instead, a computationally more efficient approach is to choose $\hat{p}^{t}$ as the sample mean of $\tilde{\mathbf{Y}}_{1:\tau}$, i.e. $\hat{p}^{t}=\frac{1}{\tau}\sum_{i=1}^{\tau}\hat{\mathbf{Y}}^{t}_{i}$, where $\hat{\mathbf{Y}}^{t}_{i}$ is the $i^{\rm th}$ vector in $\tilde{\mathbf{Y}}_{1:\tau}$. We conjecture that one can derive a similar regret bound with this modification, but leave the analysis to future work. Moreover, we believe that similar approximate Thompson sampling algorithms and regret bounds can be developed for more general sequential decision problems, such as multi-armed bandits with unbounded noises and episodic reinforcement learning, but leave them to future work.

We provide a proof sketch for Theorem 5.1 in this subsection. First, notice that the expected per-step regret at time $t$ is $\mathbb{E}[p_{A^{*}}-p_{A_{t}}]$, which can be decomposed as

Recall that action $\tilde{A}$ is the learning target. We bound the two terms in the righthand side of equation (9) separately. First, based on the fact that $p$ and $\tilde{p}$ are conditionally i.i.d given the environment proxy $\tilde{\mathbf{Y}}_{1:\tau}$, we can show that

To bound the second term $\mathbb{E}[p_{\tilde{A}}-p_{A_{t}}]$, we consider its conditional version $\mathbb{E}_{t}[p_{\tilde{A}}-p_{A_{t}}]$, where the subscript $t$ denotes conditioning on the history $H_{t}$. Using information-ratio analysis, we can prove that

Using Pinsker’s inequality, the data processing inequality, and the assumption on the expected KL-divergence in Theorem 5.1, we can bound that

On the other hand, based on Cauchy–Schwarz inequality and the chain rule for mutual information, we have

Finally, note that $\mathbb{I}(\tilde{A};H_{T})\leq\mathbb{H}(\tilde{A})\leq\log K$. Combining the above inequalities, we have proved Theorem 5.1.