Information Directed Sampling for Linear Partial Monitoring

Introduction

Partial monitoring is an expressive framework for sequential decision making in which the learner does not directly observe the reward (Rustichini, 1999). Instead, the learner obtains observations from pre-specified observation distributions that are associated to the actions and may or may not provide direct information about the reward. In this work, we consider a stochastic version of the problem with a linear reward and observation model, which is sometimes referred to as combinatorial partial monitoring (Lin et al., 2014; Chaudhuri and Tewari, 2016). Among other settings as described in Section 4, the linear partial monitoring model strictly generalizes linear bandits (Abe and Long, 1999; Auer, 2003), combinatorial bandits (Cesa-Bianchi and Lugosi, 2012) both with bandit and semi-bandit feedback, and some variants of dueling bandits (Yue and Joachims, 2009).

where $x^{*}=\operatorname*{arg\,max}_{x\in\mathcal{X}}\langle x,\theta\rangle$ is the optimal action, chosen arbitrarily whenever the choice is not unique. A slightly more general formulation of the setup is in Appendix A.1, which we will use for some applications. Bandit games are a special case where $A_{x}=x$. We discuss further applications in detail in Section 4. Readers seeking further motivation and intuition for the setup will benefit from skipping ahead to this section.

A linear partial monitoring game is called finite if it has finitely many actions. An action $x\in\mathcal{X}$ is called Pareto optimal if it is an extreme point of the convex hull of $\mathcal{X}$. The set of actions that are optimal for $\theta$ is

Information Directed Sampling

We propose a new algorithm for stochastic linear partial monitoring based on the information directed sampling (IDS) principle. This strategy uses the observations $a_{t}=A_{x_{t}}^{\top}\theta+\epsilon_{t}$ to construct conservative estimates $\Delta_{t}(x)\geq\langle x^{*}-x,\theta\rangle$ of the true gaps and an associated information gain $I_{t}(x)$, detailed below. The information gain quantifies the uncertainty reduction in the parameter estimate when the learner chooses $x\in\mathcal{X}$ and observes $A_{x}^{\top}\theta+\epsilon$. IDS is the policy that samples action $x_{t}$ from a distribution $\mu_{t}$ that minimizes the information ratio,

Our Contributions

Related work

Notation

Assumptions

Information Directed Sampling for Linear Partial Monitoring

Information directed sampling (IDS) was introduced by Russo and Van Roy (2014) for the Bayesian bandit setting. IDS samples actions from a distribution that minimizes the ratio of squared expected regret and mutual information. The information ratio appears in a sum under the square root in the regret bound and IDS is the policy that (greedily) minimizes this term. Kirschner and Krause (2018) introduced a frequentist analog of the algorithm that replaces the Bayesian expected suboptimality and information gain with frequentist counterparts and exhibits high-probability regret bounds on linear bandits. In the following we generalize the latter approach, which we simply refer to as IDS.

The minimizing distribution is well defined and can always be chosen with a support of two actions. Furthermore, $\mu\mapsto\Psi_{t}(\mu)$ is convex. These results were previously shown for the bandit setting by Kirschner and Krause (2018, Lemma 4,16,17) and continue to hold in the more general setting. We briefly discuss computational concerns in Section 5.

Let $A_{t}=A_{x_{t}}$ be the observation operator for the action chosen in round $t$. To estimate the gap $\Delta_{t}(x)$, IDS uses the regularized least squares estimator, which after $t$ rounds is

where $V_{t}=\sum_{s=1}^{t}A_{s}A_{s}^{\top}+\mathbf{1}_{d}$. Define a sequence of confidence sets $(\mathcal{C}_{t})_{t=0}^{n}$ by

The concentration bound by Abbasi-Yadkori et al. (2011, Theorem 2) shows that with probability at least $1-\delta$ it holds that $\theta\in\mathcal{C}_{t}$ for all $t$. Our estimate of the suboptimality gap is defined as

which is chosen so that with high probability $\langle x^{*}-x,\theta\rangle\leq\Delta_{t}(x)$ for all $x\in\mathcal{X}$ and all rounds $t$. Note that $\Delta_{t}(x)\geq 0$ for all $x\in\mathcal{X}$. For the information gain we use

The definition corresponds to the usual Shannon mutual information when using a Gaussian prior on the parameter and a Gaussian likelihood function. For the bandit setting, it was previously demonstrated by Kirschner and Krause (2018) that the choice of $I_{t}$ can have a large impact on empirical performance. In Appendix B we discuss some alternative choices for both $\Delta_{t}$ and $I_{t}$.

The regret of any strategy can be bounded in terms of the cumulative sum of the information ratio $\sum_{t=1}^{n}\Psi_{t}(\mu_{t})$ and the total information gain, $\gamma_{n}=\sum_{t=1}^{n}I_{t}(x_{t})$. The following result is a generic regret bound that generalizes Theorem 1 of Kirschner and Krause (2018). Note that for deterministic policies the result can be simplified (Kirschner and Krause, 2018, cf. Theorem 2).

For $\eta\geq 0$, let $G_{\eta}=\{t\in[n]:\Delta_{t}(\mu_{t})\leq\eta\}$. There exists a universal constant $C>1$ such that for any $n\geq 1$ with probability at least $1-\delta$ the regret of any (possibly) randomized policy $(\mu_{t})_{t=1}^{n}$ is bounded by

For the proof, note that $\langle x^{*}-x_{t},\theta\rangle\leq\Delta_{t}(x_{t})$ and consider the sum over the expected gap estimates,

where we used the definition of $G_{\eta}$ and the Cauchy–Schwarz inequality. A variance-dependent martingale bound such as Freedman’s inequality shows that the regret $R_{n}$ concentrates on the sum over (conditional) expected regret up to an additive $\mathcal{O}(\log n)$ term and the total expected information gain is bounded by $\sum_{t=1}^{n}I_{t}(\mu_{t})\leq c(\gamma_{n}+\log\frac{1}{\delta})$. The complete proof is given in Appendix A.3.

The next lemma is a standard result (Abbasi-Yadkori et al., 2011, cf. Lemma 10) and shows that for fixed dimension, the total information gain depends only logarithmically on the horizon.

For the information gain $I_{t}$ as defined in (4), $\gamma_{n}=\log\det(V_{n})-\log\det(V_{0})\leq d\log\left(1+\tfrac{nm}{d}\right)$ and $\beta_{n}=\sqrt{\gamma_{n}+2\log\tfrac{1}{\delta}}+1$.

Importantly, $\gamma_{n}$ and $\beta_{n}$ have no dependence on the number of actions. Further, if $\theta\in\mathcal{H}$ is contained in a reproducing kernel Hilbert space $\mathcal{H}$ with bounded Hilbert norm $\|\theta\|_{\mathcal{H}}\leq 1$ (corresponding to a Gaussian process), even the dependence on $d$ can be avoided (Srinivas et al., 2010).

2 Regret Bound for Globally Observable Games

We first analyze globally observable games (see Eq. 1). The condition implies that $\langle x-y,\theta\rangle$ can be estimated from data collected by the algorithm using appropriate actions. The game-dependent constants that appear in the analysis depend on the degree to which the learner can efficiently gain information, which roughly depends on how well the observation operators $A_{x}$ are aligned with a direction $x-y$ in which we try to improve the accuracy of our estimation. We define the worst-case alignment constant as

Note that for games that are globally observable, $\alpha$ is always bounded, independent of the number of actions (Lemma A.6, Appendix A.6).

For any game that satisfies the global observability condition (1), there exists a universal constant $C>0$ such that for any $n\geq 1$ with probability at least $1-\delta$,

The greedy action $\hat{x}^{*}_{t}=\operatorname*{arg\,max}_{x\in\mathcal{X}}\langle x,\hat{\theta}_{t-1}\rangle$ satisfies $\Delta_{t}(\hat{x}^{*}_{t})^{2}\leq 2\alpha\beta_{t-1}\max_{z}I_{t}(z)$.

Let $w_{t}=\operatorname*{arg\,max}_{w\in\{x-y:x,y\in\mathcal{X}\}}\|w\|_{V_{t-1}^{-1}}^{2}$ be the most uncertain direction. Then,

Note three ways to write $\|w\|_{V_{t-1}^{-1}}^{2}=\|V_{t-1}^{-1/2}w_{t}\|^{2}=\langle w_{t},V_{t-1}^{-1}w_{t}\rangle$. Basic linear algebra shows that

For the last step we used the inequality $a\leq 2\log(1+a)$ for $a\in$ and that the eigenvalues of $A_{z}^{\top}V_{t-1}^{-1}A_{z}$ are bounded in $$by the assumption$\|A_{z}\|\leq 1$and$V_{t-1}^{-1}\preceq\mathbf{1}_{d}$. With the most informative action$z_{t}=\operatorname*{arg\,max}_{x\in\mathcal{X}}I_{t}(x)$, it follows that

The following lemma shows that IDS never plays a distribution that is too far from greedy. The proof is deferred to Appendix A.4.

Let $\mu_{t}$ be the IDS distribution at time $t$. Then $\Delta_{t}(\mu_{t})\leq 2\min_{x\in\mathcal{X}}\Delta_{t}(x)$.

of Theorem 2.3 Let $z_{t}=\operatorname*{arg\,max}_{x\in\mathcal{X}}I_{t}(x)$ be the informative action. For $p\in$, let $\mu(p)=(1-p)\delta_{\hat{x}^{*}_{t}}+p\delta_{z_{t}}$ be the distribution that randomizes between the greedy and the informative action. By definition, the information ratio of IDS is bounded by the ratio of $\mu(p)$,

The second inequality uses $\Delta_{t}(z)\leq 1$, $I_{t}(\hat{x}_{t}^{*})\geq 0$ and Lemma 2.4 to bound $\Delta_{t}(\hat{x}^{*}_{t})^{2}\leq 2\alpha\beta_{t-1}I_{t}(z)$. The third inequality follows by choosing $p=\Delta_{t}(\hat{x}_{t}^{*})\in$ and the last follows from Lemma 2.6. Next, Lemma 2.1 shows that with probability at least $1-\delta$,

where we used the fact that $(\beta_{t})_{t=0}^{n}$ is non-decreasing. Optimizing $\eta$ completes the proof.

3 Regret Bound for Locally Observable Games

In globally observable games, the learner can estimate the gaps for all actions, but may need to play actions that are known to be suboptimal. The definition of local observability (see Eq. (2)) means that the learner can gain information while playing only actions that appear plausibly optimal.

Recall the definition of the confidence set $\mathcal{C}_{t}$ in Eq. 3 and let $\mathcal{P}_{t}=\mathcal{P}(\mathcal{C}_{t-1})$ be the set of actions that are plausibly optimal in round $t$. Again, our bound depends on the signal to noise ratio when exploring. For a set of (plausible optimal) actions $\mathcal{Y}\subset\mathcal{X}$, define the worst-case alignment for $\mathcal{Y}$,

For locally observable games denote $\alpha_{t}=\alpha(\mathcal{P}_{t})$. There exists a universal constant $C>0$ such that for any $n\geq 1$ with probability at least $1-\delta$,

We show in Appendix G that on locally observable games with more than one Pareto optimal action, any algorithm suffers $\Omega(n^{1/2})$ regret in the worst case. To prove the upper bound, the first step is to construct an exploration distribution that is supported on the plausible maximizers $\mathcal{P}_{t}$ and has a constant information ratio. Note that IDS is not restricted to playing actions within $\mathcal{P}_{t}$, nor is it required to explicitly compute this set. In fact, actions that are not plausible maximizers can have a better trade-of between regret and information.

For locally observable games, there exists an exploration action in $\mathcal{P}_{t}$ such that,

The complete proof is in Appendix A.5. The argument shows that for plausible maximizers $x\in\mathcal{P}_{t}$, $\Delta_{t}(x)^{2}\leq 4\beta_{t-1}\max_{y\in\mathcal{P}_{t}}\|y-x\|_{V_{t-1}^{-1}}^{2}$ and is otherwise similar to the proof of Lemma 2.4.

of Theorem 2.8 Let $z_{t}=\operatorname*{arg\,max}_{x\in\mathcal{P}_{t}}I_{t}(x)$ be the most informative action in the current plausible maximizer set $\mathcal{P}_{t}$. By Lemma 2.9,

Invoking the general IDS bound (Lemma 2.1) with $\eta=0$ completes the proof.

4 Smooth Convex Action Sets

Assume that $\mathcal{X}$ is closed, convex, has a non-empty interior and that $h_{\mathcal{X}}$ is twice differentiable. Suppose furthermore that the game is globally observable according to Eq. 1 and has strictly positive principle curvature everywhere:

Then, with probability at least $1-\delta$, for any $n\geq 1$,

where $C$ is a constant depending only on $(A_{z}:z\in\mathcal{X})$.

The proof is given in Appendix D. The key argument shows that $\Delta_{t}$ applied to the empirically optimal action scales like the square of the diameter of the confidence set. This compares favorably with the case without curvature, where the error is about linear in the diameter of the confidence set.

5 Contextual Partial Monitoring Games

The contextual bandit problem is a well known extension of the bandit setting where the learner receives a context before choosing the action (Woodroofe, 1979; Langford and Zhang, 2008). We introduce a novel contextual variant of linear partial monitoring, that strictly generalizes the linear contextual bandit setting. Let $\mathcal{Z}$ be a compact set of contexts. Each context $z\in\mathcal{Z}$ defines a partial monitoring game with action set $\mathcal{X}_{z}$ and the observation operators $\{A_{x}^{z}\}$, where the map $(x,z)\mapsto A_{x}^{z}$ is assumed to be continuous. At time $t$, the learner receives a context $z_{t}\in\mathcal{Z}$ and chooses an action $x_{t}\in\mathcal{X}_{z_{t}}$. The reward is $\langle x_{t},\theta\rangle$ and the observation is $a_{t}=A_{x_{t}}^{z_{t}\top}\theta+\epsilon_{t}$ where the parameter $\theta$ is the same in every context. The objective is to compete with the best in-hindsight policy that maps context to actions. Regret is defined with respect to the context-dependent solution $x_{t}^{*}=\operatorname*{arg\,max}_{x\in\mathcal{X}_{z_{t}}}\langle x,\theta\rangle$:

The regret of the learner depends on the sequence of contexts observed and the corresponding sequence of partial monitoring games which share the common parameter $\theta$. All our notions extend with the contextual argument,

Conditional IDS is the policy that minimizes the $\mu_{t}=\operatorname*{arg\,min}_{\mu\in\mathscr{P}(\mathcal{X})}\Psi(\mu,z_{t})$ conditioned on the observed context. The next result extends the regret guarantees for locally and globally observable games to the contextual setting by making strong assumptions on the sequence of games defined by the context. We refer to Appendix E.1 for our formal result.

(Informal) If the sequence of games defined by the observed contexts $z_{1},\dots,z_{n}$ are globally observable, conditional IDS achieves R_{n}\leq\mathcal{O}\big{(}n^{2/3}(\alpha\beta_{n}(\gamma_{n}+\log\tfrac{1}{\delta}))^{1/3}\big{)} regret with high probability. If the sequence of games is uniformly locally observable, then conditional IDS achieves $R_{n}\leq\mathcal{O}\left((\alpha_{0}\beta_{n}(\gamma_{n}+\log\frac{1}{\delta})n)^{1/2}\right)$.

Perhaps surprisingly, the contextual case allows for much weaker conditions under which no-regret is possible if the learner exploits the distribution of contexts. Here we study the case where the context follows a known distribution $\nu\in\mathscr{P}(\mathcal{Z})$; the case where the distribution is unknown or the learner tries to adapt her behaviour towards an arbitrary sequence is left as an interesting direction for future work. It is instructive to think about some examples:

An extreme case is where for some $z\in\mathcal{Z}$ the learner obtains no information ($A_{x}^{z}=0$ for all $x\in\mathcal{X}_{z}$). In such rounds the only sensible choice is the greedy action. Exploration needs to happen in rounds where information is available and needs to be sufficiently diverse to account for rounds where the learner is forced to play greedily. Note that while there can be vanishing information gain in some rounds, the expected information gain, that takes the distribution $\nu$ over the context into account, is non-zero.

Since also the greedy action depends on the random context, there can be cases where the learner incurs sufficient exploration by playing mostly greedy. This effect has been studied in the bandit literature before (Bastani et al., 2017; Hao et al., 2019).

Conditional IDS does not depend on the distribution $\nu$ and it is easy to see that it can behave suboptimally in both examples. To include the randomness of the context within the IDS framework, consider a joint distribution $\xi\in\mathscr{P}(\mathcal{X}\times\mathcal{C})$ over context and actions with marginal $\xi_{z}\in\mathscr{P}(\mathcal{Z})$. As before, $\Delta_{t}(\xi)$ and $I_{t}(\xi)$ extend linearly. At time $t$, contextual IDS computes a distribution $\xi$ with marginal $\xi_{z}=\nu$, that minimizes the joint ratio,

The action is sampled from $x_{t}\sim\xi_{t}(x|z_{t})$ after observing $z_{t}$. In the joint minimization of the information ratio the contextual distribution $\nu$ contributes to exploration and a smaller information ratio. The intuition is that to estimate along a direction $x-y$ in a contextual action set $x,y\in\mathcal{X}_{z}$, the learner can wait for a different context $z^{\prime}$ to be realized where $x-y$ can easily be estimated and at low cost. This leads to the following condition that defines globally observable contextual games:

thus it suffices that a direction $x-y$ in $\mathcal{X}_{z}$ can be estimated under some context $z^{\prime}\in\mathcal{Z}$ that appears with non-zero probability $\nu(z^{\prime})$. The next result quantifies the rate in globally observable games.

For globally observable contextual games with bounded expected worst-case alignment $\alpha(\nu)$, for any $n\geq 1$, the regret is bounded with probability at least $1-\delta$,

All proofs and details for this result can be found in Appendix E.2 and the analogous result for the locally observable case is in Appendix E.3.

Classification of Finite Games

The minimax regret for any finite linear partial monitoring game satisfies

The classification theorem is proven by combining upper and lower bounds, carefully checking that all cases have been covered. We further show in Appendix F that our definitions of local and global observability coincide with the standard notions in finite partial monitoring that are based on the neighborhood graph, as well as the notion of a global observer set used by Lin et al. (2014).

Applications and Extensions

The framework of linear partial monitoring captures many applications and models for sequential decision making that were previously studied in the literature. We outline some of them below and provide additional details in Appendix C.

Linear Bandits

Dueling Bandits

Combinatorial Bandits

This is the original motivation for the linear partial monitoring setting by Lin et al. (2014) and Chaudhuri and Tewari (2016) and leads to games that are either locally or globally observable. We refer to the previous works for further applications. Our formulation covers combinatorial bandits both with bandit and semi-bandit feedback. An important special case is the batch setting (Appendix C.4).

Transductive and Starved Bandits

The transductive linear bandit setting was recently proposed by Fiez et al. (2019). The learner has access to a set of actions that is dedicated for exploration, while the objective is to achieve low regret on a different, target set of actions. It was open to find an approach that minimizes cumulative regret, which we effectively resolve (Appendix C.2). Similar in spirit are starved bandits (Bubeck et al., 2018), where the learner only obtains information when sampling actions from a pre-defined distribution. This setting is closely connected to our contextual setting (see Appendix C.3) and the regret bounds on convex action sets in Section 2.4.

Product Testing and Invasive Measurements

An early toy example for a globally, but not locally observable game is that of “apple tasting” (Cesa-Bianchi et al., 2006). In this task, the learner optimizes a production chain with the option to remove a product for inspection (and destroying it in the process). Other applications include parameter tuning of experimental facilities such as particle accelerators (Kirschner et al., 2019), where invasive measurement devices provide a very rich signal at the expense of voiding any downstream measurements (for a stylized version of this problem and a numerical demonstration of IDS, see Appendix C.6).

Kernelized Partial Monitoring

Our approach and the analysis extend to the kernelized setting, where the reward function is in a known reproducing kernel Hilbert space (RKHS). This includes kernelized bandits (Srinivas et al., 2010; Abbasi-Yadkori, 2012; Chowdhury and Gopalan, 2017), also known as Bayesian optimization, as a special case. Interesting applications beyond the bandit setting include Bayesian optimization with gradients (Wu et al., 2017b) or even Hessian evaluations (Wu et al., 2017a). Unlike previous results, our approach leverages all available information and achieves a strong finite time convergence guarantee. We refer the reader to Appendix C.6 for a detailed introduction and formal statements. In the limit with continuous action sets, dueling bandits can be understood as global optimization where the learner has access only to the gradient.

Discussion

We introduced information directed sampling for stochastic linear partial monitoring, which – to the best of our knowledge – is the first approach that achieves the optimal regret rate in all finite linear games. Our classification theorem provides a complete picture of the achievable worst-case regret rates in finite linear games. Nevertheless, many directions are left for future work. Proving non-trivial instance-dependent regret bounds for IDS is an important open question, even for the standard linear bandit setting. Another challenge is to find precise observability conditions that capture the rate achievable on continuous action sets.

For a naive implementation of IDS for finite games, the computational complexity per step is $\mathcal{O}(d|\mathcal{X}|^{2})$, which is required to compute all gap estimates. The exact IDS distribution can be found by iterating over pairs of actions (a solution supported on two actions always exists). Alternatively a standard convex solver can be used to minimize the information ratio over the probability simplex. With a weaker regret estimate (Appendix B.1), the action minimizing the information ratio can be found in $\mathcal{O}(|\mathcal{X}|)$, which matches the computational cost of index based approaches for bandits like UCB. For larger or continuous action sets, some previous approaches rely on oracle solvers (Lin et al., 2014; Chaudhuri and Tewari, 2016) and for the bandit setting, Thompson sampling is a well-known oracle efficient method (Agrawal and Goyal, 2013; Abeille and Lazaric, 2017). Given the generality of our results, finding an oracle-efficient approximation of IDS is an important task for future work.

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme grant agreement No 815943.

References

Appendix A Additional Lemmas and Proofs

A.2 Finite Partial Monitoring

Unlike the standard finite and linear bandit frameworks, finite partial monitoring is not quite a special case of the linear setting. On the one hand, our setting permits infinite observation (and action) spaces, which are not usually covered by existing results. On the other hand, the assumptions of our setting mean the algorithm does not recover known bounds for algorithms in the finite unstructured setting. The main reason is that we do not restrict $\theta$ except in terms of $\left\lVert\theta\right\rVert\leq 1$, while in the finite setting the $\theta$ is effectively constrained to the probability simplex. Consider the following finite game, characterized by reward and signal matrices

The signal matrix is such that the learner observes no information. Meanwhile, however, the rewards are such that the learner knows immediately that the first action is optimal, so in the finite partial monitoring literature this game is trivial and good algorithms suffer zero regret. Our algorithm, however, does not assume that $\theta$ lies in the probability simplex, and when $\theta=(-\sqrt{2},-\sqrt{2})$, the second action is clearly optimal. The different assumptions on $\theta$ mean that this game is now hopeless and algorithms consequentially suffer linear regret. size=,color=gray!20!white,]Note: Perhaps this can be resolved by intersecting the confidence set with the constraint.

A.3 Proof of Lemma 2.1

Using Freedman’s inequality one can get the following concentration result on the regret (Kirschner and Krause, 2018, Lemma 13). For any fixed $n$, with probability at least $1-\delta/2$,

The inequality follows from the definition of $G_{\eta}$ and we use Cauchy-Schwarz to bound

In the last step, we also used the non-negativity of $I_{t}(\mu_{t})$. Finally, the sum over expected information gain $\sum_{t=1}^{n}I_{t}(\mu_{t})$ is close to the realized information gain $\sum_{t=1}^{n}I_{t}(x_{t})$ with high probability. This is made precise in Lemma 3 of Kirschner and Krause (2018), which shows that if $I_{t}(x)\leq 1$, then with probability at least $1-\delta/2$, for any $n\geq 1$,

Note that our boundedness assumptions $\|A_{x}\|_{2}\leq 1$ and the fact that $V_{t}^{-1}\preceq\mathbf{1}_{d}$ imply the required assumption $I_{t}(x)\leq 1$. By definition $\gamma_{n}=\sum_{t=1}^{n}I_{t}(x_{t})$. A union bound over the previous displays completes the proof.

A.4 Proof of Lemma 2.6

By assumption, for any $p\in[0,1)$ and any $x\in\mathcal{X}$,

Since $\Psi_{t}(0)=\Psi_{t}(\mu_{t})$ and $p\mapsto\Psi_{t}(p)$ is differentiable at $p=0$ it follows that

A.5 Proof of Lemma 2.9

For the analysis it is useful to define a lower bound on the regret,

For the upper bound on the regret $\Delta_{t}(x)$, it holds that

where we restricted the maximum to plausible maximizers.

Assume that $y$ is not a plausible maximizer, i.e. $\delta_{t}(y)>0$. Then for any $\theta\in\mathcal{C}_{t}$, there exists a $z=z(\theta)\in\mathcal{X}$ s.t. $(z-y)^{\top}\theta>0$. For fixed $x\in\mathcal{X}$ we find,

Hence, the left-hand side is maximized only if $y\in\mathcal{P}_{t}$ is a plausible maximizer.

Lemma A.3 shows that we can write $\Delta_{t+1}(x)$ as follows:

The last step follows from the same argument as in the proof of Lemma 2.4, where we restrict $x,y$ to $\mathcal{P}_{t}$ and use the definition $\alpha_{t}=\alpha(\mathcal{C}_{t-1})$.

A.6 Bounds for the Alignment Constant

Further, in the bandit game (where $A_{x}=x$), $\alpha(\mathcal{P})\leq 4$.

Let $x,y\in\mathcal{P}$ with $x\neq y$. By assumption, there exists a $w$ such that $x-y=Aw$ with $w\neq 0$. Then,

In the bandit game we can choose $w_{x}=1$, $w_{y}=-1$ and $w_{z}=0,\forall z\in\mathcal{P}\setminus\{x,y\}$, hence $\alpha(\mathcal{P})\leq 4$. In general, we can choose $\mathcal{Q}\subset\mathcal{P}$ with $|\mathcal{Q}|=d$ s.t. $w_{z}=0$ for $z\in\mathcal{P}\setminus\mathcal{Q}$. Therefore (we reuse the symbol $w$ in a different dimension),

Denote $B=(A_{z}:z\in\mathcal{Q})$. The solution that minimizes the right-hand side is the ordinary least-squares solution $w^{*}=(B^{\top}B)^{\dagger}B^{\top}(x-y)$ where † denotes the pseudo inverse. Therefore, using the properties of the pseudo inverse and $\|x-y\|\leq 1$,

Appendix B Regret Estimators and Information Gain Functions

Our regret estimate $\Delta_{t}(x)=\max_{\theta\in\mathcal{C}_{t-1}}\max_{y\in\mathcal{X}}(y-x)^{\top}\theta$ is defined the tightest way for the given confidence bounds (up to truncation for bounded gaps). size=,color=gray!20!white,]Note: Can we avoid truncation? An interesting fact is that $\Delta_{t}(x)$ is a convex function because the maximum is over convex functions. The estimate can be relaxed to

B.2 Directed Information Gain

size=,color=gray!20!white,]Note: Equality Statement?

The proof is an exercises in linear algebra and makes use of the Sherman-Morrison formula and the matrix determinant lemma.

The inequality follows because all eigenvalues of the matrix inside the determinant are not smaller than 1, and then the generalized matrix determinant lemma to rewrite the expression.

Let $\mathcal{Y}\subset\mathcal{X}$ be a subset of actions and let $w=x-y$ for $x,y\in\mathcal{Y}$ such that $w\in\operatorname{span}(\{A_{x}:x\in\mathcal{Y}\})$. Then the most informative action in the set $\mathcal{Y}$ satisfies

First, note that $\frac{1}{2}(\mathbf{1}_{d}+A_{z}^{\top}V_{t-1}^{-1}A_{z})\preceq\mathbf{1}_{d}$ by our assumption that $\|A_{z}\|_{2}\leq 1$, hence

Define the most uncertain direction in the set of plausible maximisers,

Our next results extends the regret bounds to the variant of IDS that uses $I_{t}(x,w_{t})$ as information function. Note that the information processing inequality (Lemma B.1) implies that $\sum_{t=1}^{n}I_{t}(x_{t};w_{t})\leq\sum_{t=1}^{n}I_{t}(x_{t})$, and therefore the bound in Lemma 2.2 on the total information gain $\gamma_{n}$ continues to hold.

IDS, defined with the directed information gain $I_{t}(x;w_{t})$, achieves for any $n\geq 1$, with probability at least $1-\delta$, R_{n}\leq\mathcal{O}\big{(}n^{2/3}(\alpha\beta_{n}(\gamma_{n}+\log\tfrac{1}{\delta}))^{1/3}\big{)} on globally observable games, and $R_{n}\leq\mathcal{O}\left((\alpha_{0}\beta_{n}(\gamma_{n}+\log\frac{1}{\delta})n)^{1/2}\right)$ on uniformly locally observable games.

The proof is the same as for Theorem 2.3 and Theorem 2.8, but uses the stronger inequality of Lemma B.3 to bound $\max_{x,y\in\mathcal{P}_{t}}\|x-y\|_{V_{t-1}^{-1}}^{2}\leq\alpha(\mathcal{P}_{t})\max_{z\in\mathcal{P}_{t}}I_{t}(x;w_{t})$.

Unlike for IDS defined with $I_{t}(x)$, the information gain $I_{t}(x;w_{t})$ requires to compute the set of plausible maximizers $\mathcal{P}_{t}=\{x\in\mathcal{X}:\delta_{t}(x)=0\}$. This can be done by computing $\delta_{t}(x)=\min_{\theta\in\mathcal{C}_{t}}\max_{y\in\mathcal{X}}\langle y-x,\theta\rangle$ for each $x\in\mathcal{X}$. Note that the minimization over $\theta$ is on a convex function and therefore can be solved efficiently. size=,color=green!20!white,]Johannes: Explain how this can be solved efficiently.

B.3 Relation to the UCB algorithm

For a bandit game, let $x_{t}^{\text{ucb}}=\operatorname*{arg\,max}_{x\in\mathcal{X}}\langle x,\hat{\theta}_{t-1}\rangle+\beta_{t-1}^{1/2}\|x\|_{V_{t-1}^{-1}}$ be the UCB action. Then,

A related result appears in (Wang et al., 2016, Lemma 2.1). The information-ratio of the UCB action is

Further, for any $x\in\mathcal{X}$, $\max_{y}\langle y,\hat{\theta}_{t-1}\rangle+\beta_{t-1}^{1/2}\|y\|_{V_{t-1}^{-1}}\geq\langle x,\hat{\theta}_{t-1}\rangle+\beta_{t-1}^{1/2}\|x\|_{V_{t-1}^{-1}}$, therefore

This shows that the UCB action minimizes the deterministic information ratio.

Appendix C Applications and Extensions

We discuss applications and extensions. Note that we make use of the generalized setup (Appendix A.1) where necessary. In this case $\mathcal{P}(\mathcal{C})\subset\mathcal{I}$ is defined to contain indexes plausible actions.

Hence $\gamma_{n}=d\log(n)$, but the ratio for the greedy action $\hat{x}_{t}^{*}$ is

C.2 Transductive Bandits

C.3 Starved Bandits

In the starved bandit setting (Bubeck et al., 2018) the learner only receives information if the action is sampled from a predefined distribution. Let $\mathcal{X}_{0}$ be a ground set of actions that, when played, yield no information ($A_{x}=0$). Denote by $\nu\in\mathscr{P}(\mathcal{X})$ the distribution that the learner can use for exploration and $z_{t}\sim\nu$ is a sample from the distribution in round $t$. The starved bandit setting is closely related to the contextual partial monitoring game with $\mathcal{G}=\mathcal{G}_{0}\cup\{(z_{t},A_{z_{t}}=z_{t})\}$ added to the set of action-observation tuples. This game is globally observable if the distribution $\nu$ is sufficiently diverse such that the samples $(z_{t})_{t=1}^{n}$ span the set of differences $\{x-y:x,y\in\mathcal{X}\}$. Note that on a curved actions set, the rate can still be $\mathcal{O}(\sqrt{n})$ as shown by Bubeck et al. (2018) (also compare our results on curved action sets in Section 2.4).

C.4 Batch Setting

The bandit batch game is locally observable with $\alpha_{0}\leq 4B^{2}$ (see Lemma A.6). The disadvantage of this formulation is, however, that the action space is exponentially large. Finding an efficient approximation of the IDS distribution is an interesting direction for future work.

C.5 Dueling Bandits with Average Reward

In words, the learner can pick any pair of actions $x_{1},x_{2}\in\mathcal{X}_{0}$, obtains the average reward $(x_{1}+x_{2})^{\top}\theta/2$ and a noisy observation of the reward difference $(x_{1}-x_{2})^{\top}\theta$. Note that the learner can also choose $(x_{1},x_{1})$ with reward $x_{1}^{\top}\theta$ and no observation. Let $\mathcal{P}(\mathcal{C})$ be a plausible set of actions. The first observation is that if $(x_{1},x_{2})\in\mathcal{P}(\mathcal{C})$ then $(x_{1},x_{1})\in\mathcal{P}(\mathcal{C})$ and $(x_{2},x_{2})\in\mathcal{P}(\mathcal{C})$, because $(x_{1}+x_{2})/2\in[x_{1},x_{2}]$ lays on the line segment between $x_{1}$ and $x_{2}$. size=,color=gray!20!white,]Note: Moreover, $(x_{1},x_{1}),(x_{2},x_{2})$ and $(x_{1},x_{2})$ are all contained in the neighborhood $\mathcal{N}_{(x_{1},x_{1}),(x_{2},x_{2})}$ (TODO: neighborhod undefined at that point). Let $(x_{1},x_{2}),(y_{1},y_{2})\in\mathcal{P}(\mathcal{C})$ be two plausible actions. We can choose a path $(z_{1},\dots,z_{l})$ with $z_{1}=x_{1}$, $z_{l}=y_{1}$ and $(z_{i},z_{i+1})\in\mathcal{P}(\mathcal{C})$. Therefore we can write

The difference $x_{2}-y_{2}$ can be written similarly, which shows that $\frac{x_{1}+x_{2}}{2}-\frac{y_{1}+y_{2}}{2}\in\operatorname{span}(A_{i}:i\in\mathcal{P}(\mathcal{C}))$. This shows that the game is locally observable. Turning to the local alignment constant

Using Lemma A.6 and the path construction above we can bound $\alpha\leq l$ or $\alpha\leq Cd$.

with the regret estimate $\Delta_{\mathcal{C}}(x)=\max_{\theta\in\mathcal{C}}\max_{j\in\mathcal{P}(\mathcal{C})}(x_{j}-x)^{\top}\theta$. Note that $\Delta_{\mathcal{C}}(x)$ is a convex function which implies that $\mathcal{P}(\mathcal{C})\subset\mathcal{Q}_{1}(\mathcal{C})\subset\mathcal{Q}_{2}(\mathcal{C})$, but equality is not true in general. The observation is that in locally observable games, we can play actions in $\mathcal{Q}_{2}(\mathcal{P}_{t})$ without worsening the regret bound. Consequently, the local alignment constant can be tightened to

Clearly, $\bar{\alpha}(\mathcal{C})\leq\alpha(\mathcal{C})$ and all regret bounds hold true with $\alpha$ replaced by $\bar{\alpha}$. For the dueling bandit game with average reward, recall that $x_{1},y_{1}\in\mathcal{P}(\mathcal{C})$ and therefore $(x_{1}+y_{1})/2\in\text{conv}(x_{1},y_{1})$, and the same holds true for $x_{2},y_{2}$. This means we can now choose $A_{(x_{1},y_{1})}=x_{1}-y_{1}$ and $A_{(x_{2},y_{2})}=x_{2}-y_{2}$ as a response to estimate along the direction $(x_{1}+x_{2})/2-(y_{1}+y_{2})/2$. We then write

and therefore, using the argument of Lemma A.6, $\bar{\alpha}(\mathcal{C})\leq 1$.

C.6 Partial Monitoring in Reproducing Kernel Hilbert Spaces

The estimate corresponds to the posterior mean of a Gaussian process (GP) model with kernel $k$ and Gaussian likelihood (c.f. Kanagawa et al., 2018). The gap estimate at time $t+1$ is defined as

The estimate is chosen such that with probability at least $1-\delta$, $f(x^{*})-f(x)\leq\Delta_{t}(x)$ for any $x\in\mathcal{X}$ and $t\geq 1$ (Abbasi-Yadkori, 2012, Theorem 3.11).

Denote by $k_{t|A_{z}}$ and $\sigma_{t|A_{z}}$ the uncertainty estimates that are (tentatively) updated with an observation generated from $A_{z}$. Such an update does not require the observation outcome $y_{t}$, similar to the linear case, where we can update the precision matrix $V_{t}|A_{z}=V_{t}+A_{z}A_{z}^{\top}$. Further, let $w_{x,y}=k_{x}-k_{y}$ be the difference of kernel features for the gap difference that we want to estimate. The kernelized directed information gain is

The kernelized variant of IDS achieves R_{n}\leq\mathcal{O}\big{(}n^{2/3}(\alpha\beta_{n}(\gamma_{n}+\log\tfrac{1}{\delta}))^{1/3}\big{)} on globally observable games and $R_{n}\leq\mathcal{O}\left((\alpha_{0}\beta_{n}(\gamma_{n}+\log\frac{1}{\delta})n)^{1/2}\right)$ on uniformly locally observable games for any $n\geq 1$ with probability at least $1-\delta$.

We illustrate a dueling bandit setting, where the learner chooses two actions $(x,x^{\prime})\in\mathcal{X}_{0}^{2}$ and observes binary feedback on $f(x)\geq f(x^{\prime})$. In the partial monitoring formulation, the observation operator is $A_{x,x^{\prime}}=k_{x}-k_{x^{\prime}}$, which means that the learner observes $\langle k_{x}-k_{x^{\prime}},f\rangle=f(x)-f(x^{\prime})$ up to noise. The learner obtains the reward of the first action (other reward models are possible), so the set of action-observation tuples is

Example: Bayesian Optimization with Gradients

The game where the learner observes only the gradient is globally observable, which means that for all $x,y\in\mathcal{X}_{0}$, $k_{x}-k_{y}\in\operatorname{span}(A_{x}^{*}:x\in\mathcal{X}_{0})$. To see this, let $\tau:\rightarrow\mathcal{X}_{0}$ be a differentiable path with $\tau(0)=x$ and $\tau(1)=y$. We claim that

This is verified, because for any $f\in\mathcal{H}$ by the fundamental theorem of calculus,

If the learner observers both the function value and the gradient, the game is locally observable.

Example: Invasive Laser Alignment

We present a numerical simulation of this setup in Figure 1. Our set $\mathcal{X}_{0}$ is discrete with 9 actions corresponding to a unit shift in any direction (or no shift). We use 25-dimensional features computed from a radial basis function kernel. In the setup where the reward signal can be observed directly, UCB outperforms IDS for the first $\sim 1000$ steps; but then IDS gains an advantage from choosing the more informative measurements from time to time. Without the direct reward observation, UCB continues to play actions that yield the integrated reward, but no longer receives any information. The parameter estimate is therefore never updated, and the UCB algorithm suffers linear regret. On the other hand, IDS still achieves no-regret through trading off the informative measurements with parameter settings that yield reward.

Appendix D Convex Action Sets

The proof of Theorem 2.11 follows by using the curvature to bound the information ratio. We will show the following:

where $C>0$ is a constant depending only on $(A_{z}:z\in\mathcal{X})$. Recall the definition of the support function $h_{\mathcal{X}}(u)=\sup_{x\in\mathcal{X}}\langle x,u\rangle$. A simple calculation shows that $\nabla h_{\mathcal{X}}(u)=\operatorname*{arg\,max}_{x\in\mathcal{X}}\langle x,u\rangle$, and $\hat{x}_{t}^{*}=\nabla h_{\mathcal{X}}(\hat{\theta}_{t})$ is the greedy action. Before the proof of the theorem we need a simple lemma bounding the regret in terms of the curvature.

Abbreviate $\eta=\theta/\left\lVert\theta\right\rVert$ and $\eta^{\prime}=\theta^{\prime}/\left\lVert\theta^{\prime}\right\rVert$. Note that for $c>0$, $h_{\mathcal{X}}(c\cdot u)=c\cdot h_{\mathcal{X}}(u)$, which implies that $\nabla h_{\mathcal{X}}(c\cdot u)=\nabla h_{\mathcal{X}}(u)$. Using the definitions,

where inequality (i) follows because $\nabla h_{\mathcal{X}}(\eta^{\prime})=\operatorname*{arg\,max}_{x\in\mathcal{X}}\langle x,\eta^{\prime}\rangle$. The second inequality (ii) follows from the definition of $\kappa_{\circ}$ and because

The last inequality (iii) follows from the following geometric inequality:

of Theorem 2.11 Let $\hat{x}_{t}^{*}=\nabla h_{\mathcal{X}}(\hat{\theta}_{t-1})$. Then, by Lemma D.1,

where the second inequality follows from the same argument as in Lemma 2.4. Hence,

The analysis of the information ratio is decomposed into two cases. The first case is when $\mathcal{C}_{t-1}$ has a large diameter, in which case the information ratio is well controlled without using curvature, and by only exploration. Suppose that

Then, using Cauchy–Schwarz inequality and the definition of $\Delta_{t}$,

Moving to the second case where Eq. 12 does not hold. Let

That $p\in$ follows by virtue of the fact that

Hence, $\mu=(1-p)\delta_{\hat{x}^{*}_{t}}+p\delta_{z_{t}}\in\mathscr{P}(\mathcal{X})$. Using that $\hat{x}_{t}^{*}=\nabla h_{\mathcal{X}}(\hat{\theta}_{t-1})$ and Lemma D.1,

Therefore, using the fact that $c\beta_{t-1}I_{t}(\mu)\geq c\beta_{t-1}pI_{t}(z_{t})\geq p\operatorname{diam}(\mathcal{C}_{t-1})^{2}$,

With the bound on the information ratio and Lemma 2.1, the proof of Theorem 2.11 follows now immediately.

Appendix E Contextual Partial Monitoring

Conditional IDS optimizes the sampling distribution for the given context $z_{t}$,

The computational complexity required to find the minimizer of the information ratio is the same as in the non-contextual case. We extend the notion of the alignment-constant with the contextual argument,

The next result is an immediate upper bound for the regret of conditional IDS under the assumption that for any context $z\in\mathcal{Z}$, each game $(\mathcal{X}_{z},\mathcal{A}_{z})$ is globally or locally observable, respectively.

If a contextual game is globally observable in the sense that for any context $z$, the game $(\mathcal{X}_{z},\mathcal{A}_{z})$ is globally observable with uniformly bounded alignment constant $\alpha(z)\leq\alpha$, then for any $n\geq 1$ with probability at least $1-\delta$, conditional IDS achieves

The corollary follows along the lines of our main results, Theorem 2.3 & 2.8. The assumptions of Corollary E.1 imply that the information ratio is bounded for any context $z$ in the respective regimes. One can achieve a slightly stronger result by replacing the alignment constant $\alpha_{0}$ with the average observed alignment $\frac{1}{n}\sum_{t=1}^{n}\alpha(\mathcal{C}_{t};z_{t})$. In this case the bound explicitly depends on the sequence of observed contexts $(z_{t})_{t=1}^{n}$ and the confidence sets $(\mathcal{C}_{t})_{t=1}^{n}$, which can lead to improved bounds in benign cases.

E.2 Regret Bounds for Contextual IDS

In this section we summarize results for contextual IDS, which minimizes

where $\nu\in\mathscr{P}(\mathcal{Z})$ is a known distribution over the set of contexts. For general compact $\mathcal{X}\times\mathcal{Z}$, Prokhorov’s theorem guarantees the existence of a minimizer (cf. Kirschner and Krause, 2018). size=,color=green!20!white,]Johannes: Measurability of kernel?

As before, this corresponds to the signal-to-noise ratio that can be achieved by choosing the best aligned observation operator $\mathcal{A}_{u}^{z}$ in context $z$, with the additional twist that learner can choose to estimate along a direction $x_{z^{\prime}}-y_{z^{\prime}}$ of a different context $z^{\prime}=g(z)$. In the next lemma, we show that the definition satisfies more intuitive upper bounds. We will see that in the finite case, the definition of the alignment constant relates to natural conditions for local and global observability.

Let $\alpha(\mathcal{C},\nu)$ be the expected alignment (14) and $\alpha(\mathcal{C},z)$ the conditional alignment (13).

For Dirac-delta distributions $\nu=\delta_{z}$,

The first inequality implies that the information ratio of contextual IDS is never worse than for conditional IDS. The second inequality captures the intuition that for every direction $x-y\in\mathcal{X}_{z}$ in a context $z$, there needs to be a context $z^{\prime}$ that appears with positive probability $\nu(z^{\prime})>0$ where $x-y$ can be estimated. The last inequality is a sanity check which shows that for a constant context, we recover the previous definitions.

For ii), denote $z^{*}=z^{*}(v,x,y)=\operatorname*{arg\,max}_{z\in\mathcal{Z}}\langle v_{z},x_{z}-y_{z}\rangle$ and define $g(z)=z^{*}$ for all $z\in\mathcal{Z}$. Then

which proves the claim. We first used the definition of $z^{*}$ and lower-bounded the expectation in the last step. The last equality iii) is immediate.

Our next result extends Lemma B.3 to account for the contextual distribution $\nu$ in the information ratio. We provide the proof for the tighter information gain $I_{t}(x,z;w)$ as defined in (9). The information processing inequality (Lemma B.1) implies the result for $I_{t}(x,z)$.

The proof is along the lines of Lemma B.3, but keeps the expectation over $\nu$. Let $g:\mathcal{Z}\rightarrow\mathcal{Z}$ be any function and $u\in\mathcal{X}$. From the proof of the mentioned lemma, we find

Let $u^{*},g^{*}=\operatorname*{arg\,max}_{u\in\mathcal{P}(\mathcal{C}),g:\mathcal{Z}\rightarrow\mathcal{Z}}I_{t}(u,\nu;w_{g})$. With this we find

With these results the regret bounds for contextual IDS follow. For simplicity, the proof is given for IDS with full information gain (4), but similar results can be obtained for the directed information gain. First, the globally observable case (Theorem 2.13, Section 2.5).

Let $x^{*}_{t}\in\mathcal{X}$ be the greedy action for each context, $x^{*}_{t}(z)=\operatorname*{arg\,max}_{x\in\mathcal{X}_{z}}x^{\top}\hat{\theta}_{t}$. Define the least accurate direction $w_{t}\in\{x-y:x,y\in\mathcal{X}\}$ in the set $\mathcal{P}_{t}$ as

Recall that $x_{t}^{*}(z)^{\top}\hat{\theta}_{t}\leq\beta_{t-1}^{1/2}\|w_{t}(z)\|_{V_{t-1}^{-1}}$. Lemma E.4 implies

The rest of argument is analogous to the proof of Lemma 2.4. Consider a sampling distribution $\mu(p)\in\mathcal{P}(\mathcal{X})$ that chooses $x^{*}_{t}(z)$ with probability $(1-p)$, and the most informative action $u(z)=\operatorname*{arg\,max}_{u\in\mathcal{X}_{z}}I_{t}(u,z)$ in context $z$ with probability $p$. By definition of the IDS policy,

We first used that $I_{t}(x_{t}^{*})\geq 0$, $\Delta_{t}(u)\leq 1$ and the inequality $2\alpha\beta_{t-1}\max_{u}I_{t}(u;\nu)\geq\Delta_{t}(x_{t}^{*};\nu)^{2}$ that we derived above. Then we optimized over $p\in$ in the last step. Similar to Lemma 2.6, one can show that IDS plays greedy most of the time. For any $x\in\mathcal{X}$,

Invoking the general bound (Lemma 2.1) and balancing the terms completes the proof.

E.3 Locally Observable Contextual Games

The condition for locally observable games is that any difference in the plausible action set $\mathcal{P}(\mathcal{C},z)$ for a context $z\in\mathcal{Z}$ can be estimated under possibly different context $z^{\prime}\in\mathcal{Z}$ by playing only actions that appear plausible optimal in the context $z^{\prime}$. Formally,

If the condition holds true, Lemma E.2 implies that $\alpha(\mathcal{C},\nu)\leq\mathcal{O}\left((\min_{z\in\mathcal{Z}}\nu(z))^{-1}\right)$ for finite action sets.

Let $w_{t}$ be the least accurate direction in the current set of plausible maximisers defined in Eq. (15). For any plausible maximiser $x\in\mathcal{P}_{t}$ it holds that

Finally, let $z_{t}=\operatorname*{arg\,max}_{x\in\mathcal{P}_{t}}I_{t}(z,\nu)$ be the most informative action that appears plausible optimal for each context. This action has bounded information ratio:

where we also used that $\alpha(\mathcal{C}_{t},\nu)\leq\alpha_{0}$ by assumption. The result follows from Lemma 2.1.

Appendix F Proof of the Classification Theorem

The classification theorem is proven by combining upper and lower bounds, carefully checking that all cases have been covered. To begin, we introduce the classification of actions that is now standard in finite partial monitoring games. The lower bounds then follow using standard techniques and are sketched in Appendix G.

For the remainder of this section we assume that $\mathcal{X}$ is finite.

The set of Pareto optimal actions is the set of extreme points $\operatorname{ext}(\text{conv}(\mathcal{X}))$ of the convex hull of $\mathcal{X}$. An action is degenerate if it is on the boundary of $\text{conv}(\mathcal{X})$, but not an extreme point. Actions in the interior of $\text{conv}(\mathcal{X})$ are called dominated. The situation is illustrated in Figure 2. Finite partial monitoring games can be completely classified by considering a graph structure known as the neighborhood graph (Lattimore and Szepesvári, 2019). Given an action $x\in\mathcal{X}$, the cell of $x$ is the set of parameters for which action $x$ is optimal:

Since $\mathcal{X}$ is finite, $\text{conv}(\mathcal{X})$ is a polytope and $C_{x}$ is either the singleton $\{0\}$ or an unbounded polytope. An action $x$ is Pareto optimal if $\dim(C_{x})=d$ and degenerate otherwise, which can be seen by observing that $C_{x}$ is the normal cone of $x$ with respect to the convex body $\text{conv}(\mathcal{X})$. Pareto optimal actions $x$ and $y$ are called neighbours if $\dim(C_{x}\cap C_{y})=d-1$, where the dimension of a polytope is defined as the dimension of the smallest affine space containing it. The neighbourhood relation defines a connected graph on the set of Pareto optimal actions. For neighboring actions $x$ and $y$ let $\mathcal{N}_{xy}=\{z:C_{x}\cap C_{y}\subseteq C_{z}\}$. Note that, besides $x$ and $y$, $\mathcal{N}_{xy}$ contains only actions $z$ with $\dim(C_{z})=d-1$. Lin et al. (2014) and Chaudhuri and Tewari (2016) use a different notion to ensure global observability and to construct an explicit exploration distribution. A global observer set is a set of actions $\mathcal{Y}\subset\mathcal{X}$ such that $\operatorname{span}(A_{x}:x\in\mathcal{Y})=\operatorname{span}(x-y:x,y\in\mathcal{X})$.

The following conditions equivalently characterize globally observable games:

For all actions $x,y\in\mathcal{X}$ it holds $x-y\in\operatorname{span}\{A_{z}:z\in\mathcal{X}\}$.

For all Pareto optimal actions $x,y$, it holds $x-y\in\operatorname{span}\{A_{z}:z\in\mathcal{X}\}$.

For the implication (ii $\Rightarrow$ i), note that Pareto optimal actions are the extreme points of $\text{conv}(\mathcal{X})$, therefore any $x\in\mathcal{X}$ can be written as a convex combination of Pareto optimal actions. (i $\Rightarrow$ iii) follows by taking $\mathcal{X}$ as global observer set. (iii $\Rightarrow$ ii) immediately follows from the definition of a global observer set.

The next lemma shows the relation of neighboring actions and local observability.

The Pareto optimal actions within $\mathcal{P}(\mathcal{C})$ are connected on the neighborhood graph.

For two Pareto optimal actions $x,y\in\mathcal{P}(\mathcal{C})$ it holds that $\mathcal{N}_{xy}\subset\mathcal{P}(\mathcal{C})$.

Any $x\in\mathcal{P}(\mathcal{C})$ can be written as convex combination of Pareto optimal actions in $\mathcal{P}(\mathcal{C})$.

The proof is intuitively simple. Take any Pareto optimal actions $x,y\in\mathcal{P}(\mathcal{C})$ and let $\theta_{x}\in C_{x}$ and $\theta_{y}\in C_{y}$. Then take the chord $[\theta_{x},\theta_{y}]\subset\mathcal{C}$ and consider the path $(x_{i})_{i=1}^{n}$ defined by the cells that intersect $[\theta_{x},\theta_{y}]\cup C_{x_{i}}\neq\emptyset$. There is a technicality that this chord may pass through intersections of cells that have dimension $d-2$. A perturbation and dimension argument fixes the proof (see Lemma F.9 below). For a similar result see (Lattimore and Szepesvári, 2019, Lemma 23).

Let $x,y\in\mathcal{P}(\mathcal{C})$ be Pareto optimal actions. Pick any $\theta\in C_{x}\cap C_{y}\cap\mathcal{C}$. If $z\in\mathcal{N}_{xy}$, we have $C_{x}\cap C_{y}\subset C_{z}$, hence $\theta\in C_{z}$ and $z$ is optimal for $\theta$. Therefore $z\in\mathcal{P}(\mathcal{C})$.

Let $F$ be the lowest dimensional face of $\text{conv}(\mathcal{X})$ containing $x\in\mathcal{P}(\mathcal{C})$. Assume that $x$ is in the interior of $F$ (otherwise it would be an extreme point and so Pareto optimal). Then let $\theta$ be a parameter such that $x$ is optimal. $H=\{z:(x-z)^{\top}\theta=0\}$ is a supporting hyperplane of $\text{conv}(F)$. Hence $F$ is a subset of $H$. Note that $H\cap\mathcal{X}\subset\mathcal{P}(\theta)$ contains actions that are optimal for $\theta$. Therefore all extreme points of $F$ are in $\mathcal{P}(\mathcal{C})$ and since $x$ is in the convex hull of the extreme points of $F$ the result follows.

The next lemma shows that observability can be characterized in terms of the neighborhood relation.

The following conditions equivalently characterize locally observable games:

For any convex $\mathcal{C}$ and all $x,y\in\mathcal{P}(\mathcal{C})$, $x-y\in\operatorname{span}\{A_{z}:z\in\mathcal{P}(\mathcal{C})\}$.

For any two neighboring Pareto optimal actions $x,y$, $x-y\in\operatorname{span}\{A_{z}:z\in\mathcal{N}_{xy}\}$.

“i) $\Rightarrow$ ii)”. Let $x,y\in\mathcal{X}$ be neighboring Pareto optimal actions. Pick $\theta\in\operatorname{relint}(C_{x}\cap C_{y})$. Then $\mathcal{N}_{xy}=\mathcal{P}(\theta)$ by Lemma F.3 and therefore $x-y\in\operatorname{span}\{A_{x}:x\in\mathcal{P}(\mathcal{C})\}$ by i).

“ii) $\Rightarrow$ i)”. Let $x,y\in\mathcal{P}(\mathcal{C})$. First note that by Lemma F.3, iii), $x-y$ can be written as linear combination of Pareto optimal actions in $\mathcal{P}(\mathcal{C})$. Therefore we can assume that $x,y$ are Pareto optimal. By Lemma F.3, i), there exists a sequence $(x_{i})_{i=1}^{m}$ of Pareto optimal actions with $x_{1}=x$ and $x_{m}=y$, such that $x_{i},x_{i+1}$ are neighbors and $\{x_{i}:i=1,\dots,m\}\subset\mathcal{P}(\mathcal{C})$. By assumption, $x_{i}-x_{i-1}\in\operatorname{span}\{A_{z}:z\in\mathcal{N}_{x_{i}x_{i-1}}\}$. Since $x-y=\sum_{i=1}^{m-1}x_{i}-x_{i+1}$ the claim follows.

Lastly, the key lemma for proving the lower bound for globally observable games shows that in games that are not locally observable, there exists a pair of neighbouring Pareto optimal actions $x,y$ and a parameter $\theta$ such that both actions $x,y$ are optimal, but $\langle x-y,\theta\rangle$ can not be estimated by playing only actions from the neighborhood $\mathcal{N}_{xy}$.

Suppose a game is not locally observable. Then there exists a pair $x,y$ of neighbouring Pareto optimal actions and $\theta\in\operatorname{relint}(C_{x}\cap C_{y})$ such that $x-y\notin\operatorname{span}\{A_{z}:z\in\mathcal{N}_{xy}\}$.

The lemma follows from the definition of local observability its equivalent charaterization provided in Lemma F.5.

The union $\mathcal{K}=\bigcup_{i=1}^{\infty}\operatorname{cl}(U_{i})$ is convex.

$\dim\left(\mathcal{K}\cap\{x:d(x,y)\leq\epsilon\}\right)=\dim(\mathcal{K})$ for all $\epsilon>0$ and $y\in U\in\mathcal{U}$.

$A=\bigcup_{U,V,W\in\mathcal{U}\text{ are distinct}}(\operatorname{cl}(U)\cap\operatorname{cl}(V)\cap\operatorname{cl}(W))$ has $\dim(A)<\dim(\mathcal{K})-1$.

We say that $U_{1},U_{2}\in\mathcal{U}$ are connected if $(\operatorname{cl}(U_{1})\cap\operatorname{cl}(U_{2}))\setminus A\neq\emptyset$. Then, for any $x\in\operatorname{cl}(U)$ and $y\in\operatorname{cl}(V)$, there exists a sequence $(U_{i})_{i=1}^{m}$ of connected sets with $U_{1}=U$ and $U_{m}=V$ and $U_{i}\cap[x,y]\neq\emptyset$.

Suppose that $x\in\operatorname{cl}(U)$ and $y\in V$. Let $B=\{z\in\mathcal{K}:d(z,y)<\epsilon\}$ with $\epsilon$ sufficiently small that $B\subset V$ and $S=\{z\in B:[z,x]\cap A\neq\emptyset\}$. A straightforward calculation shows that $\dim(S)\leq\dim(A)+1<\dim(\mathcal{K})=\dim(B)$. Hence, there exists a $z\in B\setminus S$ and $[x,z]\cap A=\emptyset$. By the last assumption, $[x,z]$ intersects with at most finitely many elements of $\mathcal{U}$, which form the path between $U$ and $V$. Next, suppose that $y\in\operatorname{cl}(V)$ and let $(y_{n})$ be a sequence in $V$ with $\lim_{n\to\infty}d(y_{n},y)=0$. By the previous argument, for each $n$, there exists a sequence $(U_{i}^{n})_{i=1}^{m_{n}}$ of connected sets with $U^{n}_{1}=U$ and $U^{n}_{m_{n}}=V$. By the fourth assumption, for suitably large $n$, there are only finitely many sets in all the $(U^{n}_{i})_{i,n}$ and hence, by re-labelling if necessary, the sequence of connected sets can be chosen so that $(U^{n}_{i})_{i=1}^{m_{n}}$ converges (in the sense that the identity/order of the sequences converges – the discrete topology on finite sequences of $\mathcal{U}$) to some sequence $(U_{i})_{i=1}^{m}$. We need to show that $\operatorname{cl}(U_{i})\cap[x,y]\neq\emptyset$ for each $i$. By the definition of convergence we have $[x,y_{n}]\cap\operatorname{cl}(U_{i})\neq\emptyset$ for all suitably large $n$. Taking a sequence $(z_{n})$ with $z_{n}\in U_{i}$ for all suitably large $n$. Compactness again allows us to assume that $(z_{n})$ converges to some $z$, which is easily seen to lie on $[x,z]$ and by closure of $U_{i}$ also lies in $U_{i}$, as required.