Stop-gradients lead to fixed point predictions

post by Johannes Treutlein (Johannes_Treutlein), Caspar Oesterheld (Caspar42), Rubi J. Hudson (Rubi), Emery Cooper (cryptophage) · 2023-01-28T22:47:35.008Z · LW · GW · 2 comments

Contents

  1. Introduction
  2. Formal setting
  3. Performative stability and game theory
  4. Repeated risk minimization and repeated gradient descent
  5. Online learning
  6. No-regret learning
  7. Prediction markets
  Appendix A. Proof of Theorem 8
  Appendix B. Proof of Proposition 11
  Appendix C. Proof of Theorem 12
  Appendix D. Armstrong's backwards-facing oracle
None
2 comments

Johannes Treutlein and Rubi Hudson worked on this post as part of SERI MATS, under the mentorship of Evan Hubinger. Rubi has also received mentorship from Leo Gao. We thank Erik Jenner for helpful discussions and Alexander Pan for bringing the performative prediction literature to our attention.

Update 30 May 2023: We have now published a paper based on our previous post [AF · GW] and this post (the material from this post is in Appendix D).

1. Introduction

In our previous post [AF · GW], we analyzed a setting in which an oracle AI is maximizing a strictly proper scoring rule while it can influence the world with its predictions about the probabilities of possible outcomes. In this setting, a prediction is called a fixed point if it accurately reflects the oracle's beliefs about the world, after having made that prediction. We showed that an oracle AI that is maximizing a strictly proper scoring rule may choose to misrepresent its beliefs and not output a fixed point, even if one exists. This is bad since, all else equal, we expect better outcomes when decisions are based on accurate rather than inaccurate reports.

In our previous analysis, we assumed that the oracle jointly optimizes both its prediction and the effect of its prediction on the world. In contrast, in this post we examine cases in which the AI only optimizes its prediction—there is a stop-gradient (Foerster et al., 2018; Demski, 2019 [AF · GW]) in front of the oracle's model of the world, which prevents optimizing outcomes directly.

This type of cognition could result, for instance, from self-supervised training on historical data. In that case, the AI may learn a robust world model, and it may learn to match its predictions to its beliefs about the world. However, the AI may never learn to optimize outcomes through its prediction, since this yields no advantage on the training data, which cannot be influenced by the AI.

Consider a situation where this oracle makes a prediction that can influence the world, and assume it models this influence correctly. Then this could put the AI in a game in which it is trying to make a prediction to match its world model, while the world model updates its beliefs conditional on the AI's prediction. What happens [AF · GW] in this game depends on the cognition learned by the AI during training. However, we show that, in contrast to the incentives discussed in our previous post, the only equilibria of this game would be fixed points. Such an oracle could thus be safer if there exists a unique safe fixed point, or if randomly chosen fixed points are likely safe.

In this post, we review and analyze several settings related to stop-gradients with the property that equilibria in them are fixed points or close to fixed points. Our goal is (i) to gain a better understanding of stop-gradient optimization in oracles and (ii) to highlight some potential training setups and agent cognitions that would lead to fixed points.

Similar ideas to the ones outlined above have been discussed in the literature on performative prediction (Perdomo et al. 2020). Performative prediction is a more general framework in machine learning in which the choice of model has an influence on the modeled distribution. Our analysis of oracle AIs is closely related and can be seen as a special case of this setting. We will indicate similarities where appropriate and make use of concepts from that literature.

First, we introduce performative stability and relate it to the game outlined above. We show that performatively stable predictions and equilibria in the game are fixed points. Second, we introduce versions of the repeated risk minimization and repeated gradient descent algorithms. We show that both lead to fixed point predictions. Third, we discuss practical methods based on repeated gradient descent that can be applied to an online learning setting, including Armstrong (2018) [AF · GW]'s backwards-facing oracle.

Finally, we discuss no-regret learning and prediction markets. We introduce a no-regret learning framework and show that policies with sublinear regret also have sublinear prediction error. In our decision market model, we show that, if the weight of each trader is small, the equilibria of the market are close to fixed points.

Oracles with stop-gradients may optimize outcomes to find fixed points, which could lead to bad consequences. Thus, the safest oracles [AF · GW] would be ones that make predictions only about aspects of the world they cannot influence. However, among oracles that can influence the world, ones with a stop-gradient are preferable for two reasons. First, they report their true beliefs, which gives us better information to base decisions on. This also enables approaches in which we ensure that there is only one safe fixed point. Second, the AI does not optimize its choice of fixed point, which is safer for the standard reasons of not wanting to optimize for an unaligned goal. Which fixed point is chosen will be contingent on initialization and specifics of the fixed point finding procedure.

2. Formal setting

Our setup is analogous to the one in our previous post [AF · GW]. We refer the reader to that post for more context. We will generalize our setting to predictions over more than two possible outcomes in an upcoming paper, but in this post we focus on binary predictions for simplicity. We believe that the results in this post generalize to higher dimensions.

An oracle reports a probability $p\in [0,1]$for a binary event. A scoring rule is a function $S:[0,1]\times \{0,1\}\to \overline{R},$ where $\overline{R}:=[-\infty ,\infty ]$ is the extended real line. Given prediction $p\in [0,1]$ and outcome $i\in \{0,1\},$ the oracle receives the score $S(p,i).$ We write 

$$S(p,q):=qS(p,1)+(1-q)S(p,0)$$

 for the expected score of predicting $p,$ given that $i$ is Bernoulli-distributed with parameter $q.$ A scoring rule $S$ is called proper if 

$$S(q,q)\ge S(p,q)$$

for all $p,q\in [0,1].$ It is called strictly proper if this inequality is strict whenever $p\ne q.$

As in the previous post, we will use a result from Gneiting and Raftery (2007, Theorem 1).

Theorem 1 (Gneiting and Raftery). Let $S$ be a scoring rule. Then $S$ is strictly proper if and only if there exists a strictly convex function $G:[0,1]\to \overline{R}$ with subderivatives $g:[0,1]\to \overline{R}$ (if $G$ is differentiable, this is just the derivative, $g\left(p\right)=G^{\prime }\left(p\right)$) such that 

$$S(p,q)=G\left(p\right)+g\left(p\right)(q-p)$$

for any $p,q\in [0,1]$.

To model the oracle's perceived influence on the world, we assume that there is a function $f:[0,1]\to [0,1]$ describing how the model's beliefs about the world, $q$, depend on its prediction, $p$. That is, we assume that $q=f\left(p\right)$. We say that $p$ is a fixed point if $f\left(p\right)=p,$ i.e., if the oracle's belief is $p,$ after updating on making the prediction $p.$

3. Performative stability and game theory

Our discussion of oracles is related to performative prediction (Perdomo et al. 2020). This is a machine learning setting where we choose a model parameter (e.g., parameters for a neural network) that minimizes expected loss (e.g., classification error). In performative prediction, the distribution over data points can depend on the choice of model parameter. Our setting is thus a special case in which the parameter of interest is a probability distribution, the loss is a scoring function, and data points are discrete outcomes. Most results in this and our previous post [AF · GW] have analogues in performative prediction.

Translated into our setting, we say that a prediction $p^{\ast }$ is performatively optimal if 

$$p^{\ast }=\underset{p}{argmax}S(p,f(p\left)\right).$$

This corresponds to the objective considered in our previous post, of an oracle that maximizes score. By results in that post, performatively optimal predictions are not necessarily fixed points.

Now consider an oracle that chooses predictions $p$ optimally given beliefs $f\left(p\right)$, but without optimizing $f\left(p\right)$ explicitly. This idea is captured by the definition of performative stability.

Definition 2 (Performative stability (Perdomo et al. 2020)). A prediction $p^{\ast }$ is called performatively stable if 

$$p^{\ast }=\underset{p}{argmax}S(p,f(p^{\ast }\left)\right).$$

Note that $f\left(p^{\ast }\right)$ is fixed when taking the maximum—there is a "stop-gradient" before $f\left(p^{\ast }\right)$ in this objective. It follows that performatively stable points are fixed points.

Proposition 3. Assume $S$ is strictly proper. Then a prediction $p^{\ast }$ is a fixed point if and only if it is performatively stable.

Proof. “$\Rightarrow$”. Assume $f\left(p^{\ast }\right)=p^{\ast }$. Then, since $S$ is proper,

$$S(p^{\ast },f(p\ast \left)\right)=S(p^{\ast },p^{\ast })\ge S(p,p^{\ast })=S(p,f(p^{\ast }\left)\right)$$

for any $p\in [0,1].$ Hence, $p^{\ast }={argmax}_{p}S(p,f(p^{\ast }\left)\right).$

“$\Leftarrow$”. Assume $p^{\ast }={argmax}_{p}S(p,f(p^{\ast }\left)\right)$. Since $S$ is strictly proper, it follows $p^{\ast }=f\left(p^{\ast }\right)$. ◻

Having introduced performative stability and related it to fixed points, we will now discuss the game from the introduction.

Definition 4 (Oracle game). Consider a two-player continuous game in which the first player controls $p\in [0,1]$ and the second player controls $q\in [0,1]$, with utility functions $U_1(p,q):=S(p,q)$ and $U_2(p,q):=-\frac{1}{2}\left(f\right(p)-q{)}^2$ for the two players, respectively.

If $p^{\ast },q^{\ast }$ is a Nash equilibrium of the oracle game, we have $p^{\ast }={argmax}_{p}S(p,q)$ and $q^{\ast }={argmax}_q-\left(f\right(p^{\ast })-q{)}^2$. Substituting the optimum value $q^{\ast }=f\left(p^{\ast }\right)$ for the second player gives us exactly above definition of performative stability. Conversely, if a prediction $p^{\ast }$ is performatively stable, then setting $q^{\ast }:=f\left(p^{\ast }\right)$ yields a Nash equilibrium.

Proposition 5. Assume $S$ is a proper scoring rule. Then for $p\in [0,1]$ and $q:=f\left(p\right)$, $(p,q)$ is a Nash equilibrium of the oracle game, if and only if $p$ is performatively stable. By Proposition 3, this is equivalent to $p$ being a fixed point.

The oracle game could be played between two submodules of an oracle, one who is responsible for making predictions and one who is responsible for updating the oracle's beliefs. Those two modules might collapse into just one big module taking a question and outputting a prediction, but it is still useful as a starting point to model them separately. Note that using the squared error for the world model is not essential here. We could also use any other function that is minimized at $q=f\left(p\right)$.

The game could also arise in an agent that uses causal decision theory to maximize its score and that believes that $S$ is influenced causally by $p$, but only acausally by $f\left(p\right)$. In that case, the only ratifiable (see Jeffrey, 1983, Ch. 1.7) decision is a Nash equilibrium of the above game. Similarly, the deliberational causal epistemic decision theory discussed by Greaves (2013) would output Nash equilibria of this game (whereas performative optimality would correspond to an agent using evidential epistemic decision theory in this case).

Perdomo et al. (2020) introduce a stackelberg version of the oracle game that produces performatively optimal instead of performatively stable reports. Consider a game in which player $1$ acts first and chooses $p$, after which player $2$ adjusts its prediction $q.$ Then player $2$ will choose $q=f\left(p\right)$, so player $1$'s optimization problem becomes 

$$p^{\ast }=\underset{p}{argmax}S(p,\underset{q}{argmax}-(q-f\left(p\right){)}^2)=\underset{p}{argmax}S(p,f\left(p\right)).$$

4. Repeated risk minimization and repeated gradient descent

Above, we have defined an alternative optimization problem and an associated game which yield fixed points, but we have not defined methods for solving these problems. In the performative prediction context, Perdomo et al. (2020) introduce repeated risk minimization and repeated gradient descent, both methods that converge to performatively stable points. In this section, we review both schemes and show how repeated gradient descent can be seen as gradient descent on a stop-gradient objective.

Here, we assume direct access to $q,$ instead of having only access to samples distributed according to $q$. In the next section, we discuss online learning when we only have access to samples. One way to understand this distinction is that the former corresponds to the internal cognition of an agent with a belief $q=f\left(p\right),$ optimizing a prediction $p.$ The latter corresponds to a machine learning training setup for an oracle, where $q$ is the ground truth distribution instead of the oracle's belief. Of course, there is no strict divide between the two. Any optimization algorithm could be used either by the agent itself or to train the agent.

First, repeated risk minimization is a procedure by which we start with a prediction $p_1$ and then iteratively update the prediction as $p_{t+1}={argmax}_{p}S(p,f(p_t\left)\right)$. Note that this is equivalent to alternating best response learning in the oracle game, where players $1$ and $2$ alternatingly optimize their actions given the action by the other player. Then player $2$'s update is $q_t=f\left(p_t\right),$ and if $S$ is strictly proper, player $1$'s update is $p_{t+1}=q_t=f\left(p_t\right).$ This shows that repeated risk minimization results in fixed point iteration on $f$. Fixed point iteration converges globally to a fixed point if $f$ has Lipschitz constant $L<1$. It also converges locally to a fixed point $p^{\ast }$ if $f$ is continuously differentiable at $p^{\ast }$ and $|f^{\prime }\left(p^{\ast }\right)|<1$.

Second, assume that $S$ is differentiable. Then repeated gradient ascent updates predictions via

$$p_{t+1}:=\Pi (p_t+\alpha E_{y\sim f\left(p_t\right)}[{\nabla }_{p}S(p_t,y)\left]\right),$$

where $E_{y\sim f\left(p_t\right)}[\cdot ]$ denotes the expectation over outcome $y$ with Bernoulli distribution with parameter $f\left(p_t\right)$, $\Pi$ is the projection onto $[0,1]$, and $\alpha >0$ is the learning rate.

Using the definition of $S$, we have 

$$E_{y\sim f\left(p_t\right)}\left[{\nabla }_{p}S\right(p_t,y\left)\right]={\nabla }_p\left(E_{y\sim q}\right[S(p_t,y)\left]\right){|}_{q=f\left(p_t\right)}={\nabla }_p\left(S\right(p_t,q\left)\right){|}_{q=f\left(p_t\right)}.$$

We can express this as 

$${\nabla }_p\left(S\right(p_t,\perp f\left(p_t\right)\left)\right):={\nabla }_p\left(S\right(p_t,q\left)\right){|}_{q=f\left(p_t\right)},$$

where, $\perp$ is the stop-gradient operator. It evaluates to the identity function but sets gradients to zero, ${\nabla }_x\left(\perp x\right)=0$ (Foerster et al., 2018; Demski, 2019 [AF · GW]). This is not a mathematical function (there is no function that is equal to the identity but has gradient zero everywhere), but rather a notational convention in reference to the stop_gradient or detach functions from tensorflow or pytorch. Interestingly, one can perform valid derivations using the stop-gradient operator (e.g., using the chain rule). We leave it to future work to explore the mathematics behind stop-gradients further.

Importantly, it matters that the gradient in repeated gradient ascent lies inside instead of outside the expectation: 

$$E_{y\sim f\left(p_t\right)}\left[{\nabla }_{p}S\right(p_t,y\left)\right]={\nabla }_p\left(S\right(p_t,\perp f\left(p_t\right)\left)\right)$$$$\ne {\nabla }_p\left(S\right(p_t,f\left(p_t\right)\left)\right)={\nabla }_p\left(E_{y\sim f\left(p_t\right)}\right[S(p_t,y)\left]\right).$$

Unlike repeated gradient ascent, the latter implements gradient ascent on $S(p_t,f(p_t\left)\right)$ and thus leads to performatively optimal reports.

Perdomo et al. (2020) show that, given their assumptions, repeated gradient descent globally converges to stable fixed points, and they provide convergence rates. We will show an analogous result relating repeated gradient ascent to fixed points in our setting, though we won't analyze global convergence.

To begin, we show that repeated gradient ascent is equivalent to naive learning (Letcher et al., 2019) in the oracle game, assuming that player $2$ always plays $q=f\left(p\right)$.

Proposition 6. Assume player $1$ is performing gradient ascent on its objective with learning rate $\alpha$, under the assumption that player $2$ plays $q=f\left(p\right)$. Then player $1$'s update is 

$$p_{t+1}=\Pi (p_t+\alpha {\nabla }_p(S(p_t,\perp f(p_t\left)\right)\left)\right).$$

Proof. The proof follows immediately from the definitions. Player $1$'s update is, by assumption, 

$$p_{t+1}=\Pi (p_t+\alpha {\nabla }_p(U_1(p_t,q)\left)\right)=\Pi (p_t+\alpha {\nabla }_p(S(p_t,q)\left)\right),$$

where $q$ is player $2$'s action. Assuming player $2$ plays $q=f\left(p_t\right)$, we get 

$$p_{t+1}=\Pi (p_t+\alpha {\nabla }_p(S(p_t,q)\left)\right)=\Pi (p_t+\alpha {\nabla }_p(S(p_t,\perp f(p_t\left)\right)\left)\right).$$

◻

Next, we show that fixed points are critical points of the fixed-point objective.

Proposition 7. Assume $S$ is proper and let $G,g$ as in the Gneiting and Raftery characterization (Theorem 1) be differentiable. Then for any $p\in [0,1],$ we have 

$${\nabla }_p\left(S\right(p,\perp f\left(p\right)\left)\right)=g^{\prime }\left(p\right)\left(f\right(p)-p).$$

In particular, if $p$ is a fixed point, it follows that ${\nabla }_p\left(S\right(p,\perp f\left(p\right)\left)\right)=0$. The reverse is true if $g^{\prime }\left(p\right)\ne 0.$

Proof. 

$${\nabla }_p\left(S\right(p,\perp f\left(p\right)\left)\right)={\nabla }_p\left(S\right(p,q\left)\right){|}_{q=f\left(p\right)}={\nabla }_p\left(G\right(p)+g(p\left)\right(q-p\left)\right){|}_{q=f\left(p\right)}$$$$=\left(g\right(p)+g^{\prime }(p\left)\right(q-p)-g(p\left)\right){|}_{q=f\left(p\right)}=g^{\prime }\left(p\right)\left(f\right(p)-p).$$

◻

Finally, we show that in our setting, repeated gradient ascent locally converges to fixed points $p^{\ast }$, with linear convergence rate, assuming that $f^{\prime }\left(p^{\ast }\right)<1$ and $g^{\prime }\left(p^{\ast }\right)>0$.

Theorem 8. Let $S$ be a strictly proper scoring rule. Let $p^{\ast }\in [0,1]$ be a fixed point of $f$ such that $G$ is twice continuously differentiable at $p^{\ast }$ and $g^{\prime }\left(p^{\ast }\right)>0$. Moreover, assume $f$ is continuously differentiable at $p^{\ast }$ and $f^{\prime }\left(p^{\ast }\right)<1$. Then, for small enough $\alpha >0$, there exists an open set $U\subset R$ with $p^{\ast }\in U$ such that for $p_1\in U\cap [0,1]$, an agent taking updates $p_{t+1}=\Pi (p_t+\alpha {\nabla }_p(S(p_t,\perp f(p_t\left)\right)\left)\right)$ will linearly converge to $p^{\ast }$.

Proof. In Appendix A. This is a standard convergence proof. Consider the discrete dynamical system defined by the agent's updates $p_{t+1}=\phi \left(p_t\right).$ By Proposition 7, it has a fixed point at $p=p^{\ast }$. We show that ${\nabla }_p\left({\nabla }_p\right(S(p^{\ast },\perp f(p^{\ast }\left)\right)\left)\right)<0$. This means that the fixed point is stable and thus the system will locally converge to it given small enough $\alpha$. ◻

5. Online learning

Now consider a machine learning setup in which we train an oracle with stochastic gradient ascent on environment samples. We assume that at time $t,$ a model makes a prediction $P_t$ and receives a score $S(P_t,Y_t),$ where $Y_t$ is Bernoulli-distributed with parameter $f\left(P_t\right).$ The model is then updated using gradient ascent on $S(P_t,Y_t).$ That is, for some learning rate schedule $({\alpha }_t{)}_t,$ we have 

$$P_{t+1}=\Pi (P_t+{\alpha }_t{\nabla }_{p}S(P_t,Y_t\left)\right).$$

We discuss this as a theoretical model for oracles trained using machine learning, to show how training setups may incentivize predicting fixed points. There are many issues [AF · GW] with the setting beyond giving accurate predictions; for instance, even if the training process sets the right incentives on training examples, the learned model may be optimizing a different objective [? · GW] when generalizing to new predictions.

To see that above setup incentivizes predicting fixed points, note that 

$$E_{Y_t\sim f\left(P_t\right)}\left[{\nabla }_{p}S\right(P_t,Y_t\left)\right]={\nabla }_p{E}_{Y_t\sim \perp f\left(P_t\right)}\left[S\right(P_t,Y_t\left)\right]={\nabla }_p\left(S\right(P_t,\perp f\left(P_t\right)\left)\right).$$

That is, the expectation of this gradient, conditional on $P_t,$ is exactly the repeated gradient from the previous section. Hence, given the right assumptions, this converges to fixed points instead of performative optima. We do not show this here, but an analogous result in performative prediction was proved by Mendler-Dünner et al. (2020).

There are several variations of this setup that essentially set the same incentives. For instance, one could also draw entire batches of outcomes $Y_{t,1:B}$ and then perform updates based on the batch gradient ${\nabla }_p{\sum }_{b=1}^{B}S(P_t,Y_{t,b}).$ This is a monte carlo estimate of the repeated gradient and thus also converges to performatively stable points and thus fixed points (Perdomo et al., 2020). One could also mix the two algorithms and, e.g., perform gradient ascent on an average of past losses, yielding a version of the backwards-facing oracle discussed in Armstrong (2018) [AF · GW]. In Appendix D, we show that that oracle can only converge to fixed points.

Note that finding fixed points depends on the fact that we differentiate $S(P_t,Y_t)$ instead of the expectation $E_{Y_t\sim f\left(P_t\right)}\left[S\right(P_t,Y_t\left)\right]=S(P_t,f(P_t\left)\right).$ If we used policy gradients to differentiate $S(P_t,f(P_t\left)\right)$, for instance, we would again optimize for performative optimality. Similarly, we could learn a Q-function representing scores for each prediction, and update the function based on randomly sampled predictions $p$. Then the Q-function would converge to estimates of $S(p,f(p\left)\right)$, and the highest Q-value would be a performative optimum. There are also some more recent papers in performative prediction that explicitly try to estimate the gradient ${\nabla }_p\left(S\right(p,f\left(p\right)\left)\right)$ and thus find performatively optimal instead of stable points (Izzo et al., 2021).

Stop-gradients could also be circumvented in a hidden way (Krueger et al., 2020). For instance, consider a hyperparameter search to meta-learn a learning algorithm, where the evaluation criterion is the accumulated loss during an episode. Then this search would prefer algorithms that optimize $S(p,f(p\left)\right)$ directly, without a stop-gradient.

Lastly, repeated gradient descent is related to decoupled approval in RL (Uesato et al., 2020). The decoupled approval policy gradient samples actions and approval queries independently and can thus differentiate with a stop-gradient in front of the approval signal. In our setting, we can differentiate through $S(P_t,Y_t)$ directly, so it is not necessary to calculate this gradient with a decoupled policy gradient. Decoupled gradients could be used to implement the stop-gradient objective if scores were discrete or otherwise not differentiable.

6. No-regret learning

In this section, we consider no-regret learning and show that algorithms have sublinear regret if and only if their prediction error is sublinear. Regret takes the environment probabilities as given and asks which predictions would have been optimal in hindsight. It thus puts a “stop-gradient” in front of those environment probabilities.

As in the previous section, we assume that at time $t\in N,$ the agent makes a prediction $P_t$ and receives a score $S(P_t,Y_t)$, where $Y_t\sim f\left(P_t\right).$ The agent's cumulative score at step $T$ is defined as ${\sum }_{t=1}^{T}S(P_t,Y_t)$. In no-regret learning, we compare performance against experts, which choose sequences of probabilities $(P_t^{\prime }{)}_t,$ $P_t^{\prime }\in [0,1]$. We assume that an expert's prediction $P_t^{\prime }$ is independent of $Y_t$ conditional on $P_t$. I.e., an expert knows the predictions $P_t$ and thus probabilities $f\left(P_t\right)$, but it does not know the outcome of $Y_t$. Let $P$ the set of all such experts.

The regret of the agent is the difference between the cumulative score received by the best expert in expectation and the cumulative score received by the agent. To define it formally, let 

$$P_t^{\ast }\in \underset{P_t^{\prime }\in P}{argmax}E\left[S\right(P_t^{\prime },Y_t)\mid P_t]=f\left(P_t\right)S(P_t^{\prime },1)+(1-f(P_t\left)\right)S(P_t^{\prime },0)$$

for $t\in N$. $P_t^{\ast }$ is a random variable that maximizes the expectation of $S(P_t^{\ast },Y_t)$ before $Y_t$ is drawn, but conditional on $P_t$.

Definition 9 (Regret). The regret of agent $(P_t{)}_t$ at time $T$ is 

$$Regret\left(T\right)=\sum _{t=1}^{T}S(P_t^{\ast },Y_t)-S(P_t,Y_t).$$

 The agent is said to have sublinear regret or no-regret if 

$$\underset{T\to \infty }{limsup}\frac{1}{T}Regret\left(T\right)\le 0.$$

First, note that we define regret relative to the best expert in expectation instead of the best expert in hindsight. The latter would always be the one that made confident predictions and accidentally got all predictions exactly right. To achieve sublinear regret, it would thus be too much to ask the agent to perform well compared to the best expert in hindsight. Moreover, for scoring rules with $S(0,0)=S(1,1),$ this expert would have a constant score $C,$ such that $\text{Regret}\left(T\right)={\sum }_{t=1}^{T}C-S(P_t,Y_t).$ This would reduce the problem to minimizing the negative score and thus finding performatively optimal predictions.

Second, we evaluate the performance of the expert with respect to the environment outcomes $Y_t$ generated by the agent $P_t,$ instead of evaluating the expert according to outcomes ${\tilde{Y}}_t\sim f\left(P_t^{\ast }\right)$ generated using their own predictions. This means that, to receive sublinear regret, the agent only has to make accurate predictions—it does not have to find a performatively optimal prediction. Our setting is thus different from the no-regret learning setup discussed in Jagadeesan et al. (2022), where regret is defined with respect to $S(P_t^{\ast },f(P_t^{\ast }\left)\right).$ In that setting, only agents converging to performatively optimal predictions have sublinear regret.

We begin by showing that the best expert in expectation actually exists, and that $P_t^{\ast }=f\left(P_t\right)$.

Proposition 10. Let $S$ be a proper scoring rule and $(P_t^{\prime }{)}_t\in P$ an expert. Then for any $t\in N,$ we have 

$$E\left[S\right(P_t^{\prime },Y_t\left)\right]=E\left[S\right(P_t^{\prime },f\left(P_t\right)\left)\right].$$

Moreover, we have $(P_t^{\ast }{)}_t=(f\left(P_t\right){)}_t$ and thus 

$$Regret\left(T\right)=\sum _{t=1}^{T}S\left(f\right(P_t),Y_t)-S(P_t,Y_t).$$

Proof. Let $t\in N$ and let $(P_t^{\prime }{)}_t\in P$ be any expert. Conditional on $P_t$, $Y_t$ has parameter $f\left(P_t\right)$ and is independent of $P_t^{\prime }$ by assumption. Hence, 

$$E\left[S\right(P_t^{\prime },Y_t\left)\right]=E\left[E\right[S(P_t^{\prime },Y_t)\mid P_t,P_t^{\prime }\left]\right]=E\left[S\right(P_t^{\prime },f\left(P_t\right)\left)\right].$$

Next, since $S$ is proper, 

$$E\left[S\right(P_t^{\prime },f\left(P_t\right)\left)\right]\le E\left[S\right(f\left(P_t\right),f\left(P_t\right)\left)\right].$$

 It follows that 

$$\underset{(P_t^{\prime }{)}_t\in P}{max}E\left[S\right(P_t^{\prime },Y_t\left)\right]=\underset{(P_t^{\prime }{)}_t\in P}{max}E\left[S\right(P_t^{\prime },f\left(P_t\right)\left)\right]\le E\left[S\right(f\left(P_t\right),f\left(P_t\right)\left)\right]=E\left[S\right(f\left(P_t\right),Y_t\left)\right].$$

Moreover, $\left(f\right(P_t){)}_t\in P$, as $f\left(P_t\right)$ is constant given $P_t$ and thus independent of $Y_t$.

It follows that, for any $t\in N,$ $P_t^{\ast }\in {argmax}_{(P_t^{\prime }{)}_t\in P}E\left[S\right(P_t^{\prime },Y_t\left)\right]$, and thus 

$$Regret\left(T\right)=\sum _{t=1}^{T}S\left(f\right(P_t),Y_t)-S(P_t,Y_t).$$

◻

If $S$ is unbounded (such as the log scoring rule), then the agent's scores can become arbitrarily low, and the limit of $\frac{1}{T}Regret\left(T\right)$ may be undefined. To simplify our analysis, we will thus assume that there is a bound on the variance of the received score $S(P_t^{\prime },Y_t)$ and on the expected score $S(P_t^{\prime },f(P_t\left)\right)$ of both the agent $(P_t{)}_t$ and the best expert $(P_t^{\ast }{)}_t$. In the case of the log scoring rule, this would be satisfied, for instance, if the agent's predictions are bound away from $0$ and $1$.

Our next proposition shows that, given these assumptions, the limit ${lim}_{T\to \infty }\frac{1}{T}Regret\left(T\right)$ exists and is nonnegative, and sublinear regret is equivalent to ${lim}_{t\to \infty }\frac{1}{T}Regret\left(T\right)=0.$

Proposition 11. Let $S$ be a proper scoring rule. Assume that ${sup}_t|S(P_t^{\prime },f(P_t\left)\right)|<\infty$ and that ${sup}_{t}Var\left(S\right(P_t^{\prime },Y_t\left)\right)<\infty$ for $P_t^{\prime }\in \{P_t,f(P_t\left)\right\}$. Then almost surely 

$$\underset{T\to \infty }{lim}\frac{1}{T}Regret\left(T\right)=\underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^{T}S\left(f\right(P_t),f(P_t\left)\right)-S(P_t,f(P_t\left)\right)\ge 0.$$

In particular, almost surely both limits exist and are finite, and the agent has sublinear regret if and only if 

$$\underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^{T}S\left(f\right(P_t),f(P_t\left)\right)-S(P_t,f(P_t\left)\right)=0.$$

Proof. In Appendix B. ◻

Now we turn to the main result for this section. We show that given our assumptions, agents have sublinear regret if and only if their prediction error is sublinear. Note that here, we do not require the $P_t$ to converge; they could also oscillate between different fixed points.

Theorem 12. Let $(P_t{)}_t$ be the sequence of the agent's predictions and $S$ a strictly proper scoring rule. Assume that ${sup}_{t}Var\left(S\right(P_t^{\prime },Y_t\left)\right)<\infty$ for $P_t^{\prime }\in \{P_t,f(P_t\left)\right\}$, and assume that there exists a compact set $C\subseteq [0,1]$ such that $P_t\in C$ for all $t$ and $S(p,f(p\left)\right)$, $S\left(f\right(p),f(p\left)\right),$ and $f\left(p\right)$ are continuous in $p$ at any $p\in C$. Then almost surely the agent has sublinear regret if and only if ${\sum }_{t=1}^T|f\left(P_t\right)-P_t|$ is sublinear, i.e., if ${lim}_{t\to \infty }\frac{1}{T}{\sum }_{t=1}^T|f\left(P_t\right)-P_t|=0$.

Proof. In Appendix C. ◻

The next result shows that if the agent's probabilities converge to some probability $p$, then $p$ must be a fixed point.

Corollary 13. In addition to the assumptions from Theorem 12, assume that $P_t$ converges almost surely to a limit ${lim}_{t\to \infty }{P}_t=p^{\ast }$. Then almost surely $p^{\ast }$ is a fixed point if and only if the agent has sublinear regret.

Proof. By Theorem 12, almost surely the agent has sublinear regret if and only if 

$$\underset{t\to \infty }{lim}\frac{1}{T}\sum _{t=1}^T|f\left(P_t\right)-P_t|=0.$$

It remains to show that, given that the $P_t$ converge, the latter is equivalent to convergence to a fixed point.

Since $C$ is compact and $P_t\in C$ for all $t\in N,$ also $p^{\ast }\in C.$ Hence, $f$ is continuous at $p^{\ast },$ so 

$$|f\left(p^{\ast }\right)-p^{\ast }|=|f\left(\underset{t\to \infty }{lim}{P}_t\right)-\underset{t\to \infty }{lim}{P}_t|=\underset{t\to \infty }{lim}|f\left(P_t\right)-P_t|.$$

Since this sequence converges, it is equal to its Cesàro mean,

$$\underset{t\to \infty }{lim}|f\left(P_t\right)-P_t|=\underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^T|f\left(P_t\right)-P_t|.$$

Hence, 

$$|f\left(p^{\ast }\right)-p^{\ast }|=\underset{t\to \infty }{lim}|f\left(P_t\right)-P_t|=\underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^T|f\left(P_t\right)-P_t|.$$

 It follows that, if ${lim}_{t\to \infty }{P}_t=p^{\ast },$ then 

$$|f\left(p^{\ast }\right)-p^{\ast }|=0\iff \underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^T|f\left(P_t\right)-P_t|=0.$$

This shows that, almost surely, $p^{\ast }$ is a fixed point, if and only if ${\sum }_{t=1}^T|f\left(P_t\right)-P_t|$ is sublinear. ◻

7. Prediction markets

Lastly, we consider prediction markets. We assume a simplified model of a prediction market, in which traders submit a single prediction and get scored using a proper scoring rule. The prediction that is output by the market and that influences the outcome is just a weighted average of the individual traders' predictions. In this situation, if a trader has a small weight and can thus barely influence the market prediction, the trader's score will mostly be determined by the accuracy of the report, rather than the influence of the report on the market. Thus, if all traders are small relative to the market, the equilibrium prediction will be close to a fixed point.

A similar result was shown by Hardt et al. (2022) in the performative prediction context. They define a firm's performative power as the degree to which the firm can influence the overall outcome with their prediction. Hardt et al. (2022) show that in an equilibrium, the distance between a player's (performatively optimal) equilibrium strategy and their strategy when optimizing loss against the fixed equilibrium distribution (here, this means predicting the market probability) is bounded by the power of the trader. We give an analogous result for our formal setting and assumptions.

To formalize the setting, assume that there are $n$ players. We associate with each player $i$ a number $w_i\in [0,1]$ such that ${\sum }_j{w}_j=1$, representing, intuitively, what fraction of the overall capital in the market is provided by player $i$. In the game, all players simultaneously submit a probability $p_i$. Then the event $Y$ occurs with probability $q=f\left({\sum }_j{w}_j{p}_j\right)$. Finally, each player is scored in proportion to $S(p_i,Y)$ for some strictly proper scoring rule $S$. Typical market scoring rules would consider terms like $S(p_i,Y)-S(p_j,Y),$ but subtracting $S(p_j,Y)$ (or multiplying by constants) does not matter for the game. We assume that players maximize their expected score, $E\left[S\right(p_i,Y\left)\right]=S(p_i,f({\sum }_j{w}_j{p}_j\left)\right).$

For discussions of market scoring rules, see Hanson 2003 and Sami and Pennock 2007. Prior work has connected these market scoring rules to more realistic prediction markets that trade Arrow--Debreu securities markets such as PredictIt (Hanson 2003; Hanson 2007; Pennock and Sami 2007, Ch. 4; Chen and Pennock 2007; Agrawal et al. 2009; Chen and Vaughan 2010).

We assume that $f$ is common knowledge. Moreover, in the following we only consider pure strategy equilibria, and we do not investigate the existence of equilibria.

Theorem 14. Let $S$ be a proper scoring rule and let $G,g$ as in the Gneiting and Raftery characterization. Let $p$ be a pure strategy Nash equilibrium of the game defined above and let $\hat{p}:={\sum }_j{w}_j{p}_j$ be the market prediction. Assume $f$ is differentiable at $\hat{p}$. For any player $i$, if $G,g$ are differentiable at $p_i$ and $g^{\prime }\left(p_i\right)\ne 0,$ it follows that 

$$|f\left(\hat{p}\right)-p_i|\le \left|\frac{w_i{f}^{\prime }\left(\hat{p}\right)g\left(p_i\right)}{g^{\prime }\left(p_i\right)}\right|.$$

Whenever $p_i\notin \{0,1\}$, the bound is tight.

In particular, this theorem shows that players $i$ with very low $w_i$ (little capital/influence on $q$) will accurately predict $f\left(\hat{p}\right)=f\left({\sum }_j{w}_j{p}_j\right)$. Note, however, that $\hat{p}$ is not necessarily a fixed point or close to a fixed point. If there are are also players $i$ with very high $w_i$, then their prediction and the overall market prediction may be wrong. (So interestingly the overall market probability ${\sum }_j{w}_j{p}_j$ is worse than the prediction of individuals. One might take this to suggest that anyone interested in $q$ should look at the latter type of predictions. Of course, if this is what everyone does, it is not so clear anymore that the model $q=f\left({\sum }_j{w}_j{p}_j\right)$ is accurate.)

Proof. The proof is analogous to the proof of Proposition 9 in our previous post [AF · GW].

For $p$ to be a pure strategy Nash equilibrium, each player must play a best response to the other player's strategies. That is, $p_i$ must be a global maximum of the function $p_i\mapsto S(p_i,{\sum }_j{w}_j{p}_j)$. Therefore, the derivative of this function must be zero if $p_i\in (0,1)$ and positive/negative if $p_i=1$/$p_i=0$.

The derivative is 

$$\begin{array}{ccc}\frac{d}{d{p}_i}S(p_i,f\left(\sum _j{w}_j{p}_j\right))& =& \frac{d}{d{p}_i}\left(g\right(p_i)(f\left(\sum _j{w}_j{p}_j\right)-p_i)+G(p_i\left)\right)\\ & =& \frac{d}{d{p}_i}\left(g\right(p_i\left)(f\left(\sum _j{w}_j{p}_j\right)-p_i)\right)+g\left(p_i\right)\\ & =& g^{\prime }\left(p_i\right)(f\left(\hat{p}\right)-p_i)+g\left(p_i\right)w_i{f}^{\prime }\left(\hat{p}\right).\end{array}$$

Now, if $p\in (0,1)$, we have 

$$0=\frac{d}{dp}S(p,f(p\left)\right)=g^{\prime }\left(p_i\right)(f\left(\hat{p}\right)-p_i)+g\left(p_i\right)w_i{f}^{\prime }\left(\hat{p}\right).$$

Rearranging terms and taking the absolute value, it follows 

$$|f\left(\hat{p}\right)-p_i|=\left|\frac{w_i{f}^{\prime }\left(\hat{p}\right)g\left(p_i\right)}{g^{\prime }\left(p_i\right)}\right|.$$

Next, assume $p_i=0$ is the optimal report for player $i.$ Then we must have 

$$0\le \frac{d}{dp}S(p,f(p\left)\right)=g^{\prime }\left(p_i\right)(f\left(\hat{p}\right)-p_i)+g\left(p_i\right)w_i{f}^{\prime }\left(\hat{p}\right).$$

By Theorem 1, $G$ is convex and thus $g^{\prime }\left(p\right)\ge 0.$ Hence, the above is equivalent to $p_i-f\left(\hat{p}\right)\ge w_i{f}^{\prime }\left(\hat{p}\right)g\left(p_i\right)/g^{\prime }\left(p_i\right)$. Since $p_i=0$, it follows $p_i-f\left(\hat{p}\right)\le 0$. Hence, $|p_i-f(\hat{p}\left)\right|\le \left|\frac{w_i{f}^{\prime }\left(\hat{p}\right)g\left(p_i\right)}{g^{\prime }\left(p_i\right)}\right|.$

Finally, if $p=1$, then analogously $p_i-f\left(\hat{p}\right)\le w_i{f}^{\prime }\left(\hat{p}\right)g\left(p_i\right)/g^{\prime }\left(p_i\right),$ and since $p=1,$ it follows again $|p_i-f(\hat{p}\left)\right|\le \left|\frac{w_i{f}^{\prime }\left(\hat{p}\right)g\left(p_i\right)}{g^{\prime }\left(p_i\right)}\right|.$ This concludes the proof. ◻

Corollary 15. In addition to the assumptions from Theorem 14, assume that $f$ is Lipschitz-continuous and that $C:={sup}_{p\in [0,1]}\left|\frac{g\left(p\right)}{g^{\prime }\left(p\right)}\right|<\infty .$ Let $p$ be a Nash equilibrium and let $ϵ>0$ arbitrary. Then there exists a $\delta >0$ such that if for all $i$, $w_i<\delta ,$ all of $p_i$ and $f\left(p_i\right)$, for all $i$, as well as ${\sum }_j{w}_j{p}_j$ and $f\left({\sum }_j{w}_j{p}_j\right),$ are within $ϵ$ of each other.

Proof. Let $ϵ>0$ arbitrary. Let $L$ be the Lipschitz constant of $f$ and note that then $|f^{\prime }\left(p\right)|\le L$ for all $p\in [0,1].$ By Theorem 14, it follows for $\hat{p}:={\sum }_j{w}_j{p}_j$ and any player $i$ that 

$$|f\left(\hat{p}\right)-p_i|\le w_{i}LC.$$

Now let $\lambda :=min\left(\right\{1,\frac{1}{L}\left\}\right)$ and $\delta :=\frac{ϵ\lambda }{4CL}.$ Then, assuming $w_i<\delta$ for all $i,$ it follows 

$$|f\left(\hat{p}\right)-p_i|\le \delta LC\le \frac{\lambda }{4}ϵ.$$

Moreover, since $\hat{p}$ is a convex combination of probabilities $p_i,$ it follows that also 

$$|f\left(\hat{p}\right)-\hat{p}|\le \underset{i}{max}|f\left(\hat{p}\right)-p_i|\le \frac{\lambda }{4}ϵ.$$

Thus, by the triangle equality, we have $|p_i-\hat{p}|\le \frac{2\lambda }{4}ϵ,$ and since $f$ is Lipschitz-continuous,

$$|f\left(\hat{p}\right)-f\left(p_i\right)|\le L|\hat{p}-p_i|\le L\frac{2\lambda }{4}ϵ\le \frac{1}{2}ϵ$$

for any $i.$

This shows that all of $p_i,\hat{p},f\left(p_i\right)$ are within $\frac{1}{2}ϵ$ of $f\left(\hat{p}\right)$ and thus by the triangle inequality within $ϵ$ of each other. This concludes the proof. ◻

It would be interesting to extend these results. For example, it's already not so clear if the players make predictions repeatedly. (To keep things simple, one should probably still imagine that all players know $f$ and that the environment probability is determined by $f$ applied to the majority forecast. If the traders have private information, prediction markets become harder to analyze. For some discussions, see Ostrovsky 2012, Chen and Waggoner 2016.)

Appendix A. Proof of Theorem 8

We use the following theorem, adapted from "Iterative Solution of Nonlinear Equations in Several Variables" (Ortega and Rheinboldt, 2000).

Theorem 16 (Ostrowski). Assume that $\phi :D\subseteq R^n\to R^n$ has a fixed point $x^{\ast }\in int\left(D\right)$ and is continuously differentiable at $x^{\ast }$. If $|\mu |<1$ for all eigenvalues $\mu$ of ${\phi }^{\prime }\left(x^{\ast }\right)$, then there exists an open set $U\subseteq D$ with $x^{\ast }\in U$ such that for any $x^0\in U$, letting $x^k=\phi \left(x^{k-1}\right)$ for $k\in N,$ it is $x^k\in U$ for all $k$ and $x^k$ converges at least linearly to $x^{\ast }$.

To begin, assume that $p^{\ast }\in [0,1]$ is a fixed point of $f$, that $f$ is continuously differentiable at $p^{\ast }$, and that $f^{\prime }\left(p^{\ast }\right)<1$. Moreover, let $G,g$ as in the Gneiting and Raftery representation of $S$, and assume that $G$ is twice continuously differentiable at $p^{\ast }$ and thus $G^{\prime \prime }=g^{\prime }$ is continuous at $p^{\ast }$.

Define the function 

$$\phi :[0,1]\to R,p\mapsto p+\alpha {\nabla }_p\left(S\right(p,\perp f\left(p\right)\left)\right).$$

Note that the agent's update rule is then $\tilde{\phi }$ defined via $\tilde{\phi }\left(p\right):=min\{1,max\{0,\phi \left(p\right)\left\}\right\}$.

First, by Proposition 7, we know that for any $p^{\ast }\in [0,1],$ we have ${\nabla }_{p}S(p^{\ast },\perp f(p^{\ast }\left)\right)=g^{\prime }\left(p^{\ast }\right)\left(f\right(p^{\ast })-p^{\ast })$, and if $p^{\ast }$ is a fixed point of $f$, we must have $g^{\prime }\left(p^{\ast }\right)\left(f\right(p^{\ast })-p^{\ast })=0$ and hence $\phi \left(p^{\ast }\right)=p^{\ast }$. Hence, $p^{\ast }$ is a fixed point of $\phi$ and thus also of $\tilde{\phi }$.

Now we will apply Theorem 16 to $\phi$. To that end, let 

$$ϵ:={\nabla }_p\left({\nabla }_{p}S\right(p^{\ast },\perp f\left(p^{\ast }\right)\left)\right).$$

Then 

$$ϵ={\nabla }_p\left(g^{\prime }\right(p^{\ast }\left)\right(f\left(p^{\ast }\right)-p^{\ast }\left)\right)=g^{\prime \prime }\left(p^{\ast }\right)\left(f\right(p^{\ast })-p^{\ast })+g^{\prime }\left(p^{\ast }\right)\left(f^{\prime }\right(p^{\ast })-1)=g^{\prime }\left(p^{\ast }\right)\left(f^{\prime }\right(p^{\ast })-1)$$

since $f\left(p^{\ast }\right)=p^{\ast }.$ Moreover, by assumption, $g^{\prime }\left(p^{\ast }\right)>0$ and $f^{\prime }\left(p^{\ast }\right)<1$. Hence, it follows that $ϵ=g^{\prime }\left(p^{\ast }\right)\left(f^{\prime }\right(p^{\ast })-1)<0$.

Now note that 

$${\phi }^{\prime }\left(p^{\ast }\right)={\nabla }_p(p+\alpha {\nabla }_p(S(p^{\ast },\perp f(p^{\ast }\left)\right)\left)\right)=1+\alpha {\nabla }_p\left({\nabla }_p\right(S(p^{\ast },\perp f(p^{\ast }\left)\right)\left)\right)=1+\alpha ϵ.$$

Hence, for small enough $\alpha >0$, it is $|{\phi }^{\prime }\left(p^{\ast }\right)|<1.$ Moreover, by assumption, $g^{\prime }\left(p^{\ast }\right)$ and $f^{\prime }\left(p^{\ast }\right)$ are continuous, so also the derivative ${\phi }^{\prime }\left(p^{\ast }\right)=1+\alpha g^{\prime }\left(p^{\ast }\right)\left(f^{\prime }\right(p^{\ast })-1)$ is continuous.

Now we can apply Ostrowski's theorem, which tells us that, if $p^{\ast }\in (0,1)$, there is an open set $U\subseteq (0,1)$ with $p^{\ast }\in U$, such that for any $p^0\in U$, the iterates $p^k=\phi \left(p^{k-1}\right)$ all lie in $U$ and $p^k$ converges at least linearly to $p^{\ast }$.

This shows that if $p^{\ast }$ is an interior point, we can choose $\alpha >0$ small enough to make sure that $F\left(U\right)\subseteq U\subseteq (0,1)$ and thus $\tilde{\phi }=\phi$ on $U$, and for $p^0\in U,$ the iteration $p^k=\tilde{\phi }\left(p^{k-1}\right)$ locally converges to $p^{\ast }$.

Now assume that $p^{\ast }=1$ (the proof for $p^{\ast }=0$ is analogous). We can extend the function $\phi$ for values $p\in (1,\infty )$ by the Whitney extension theorem. This theorem tells us that if $\phi$ is continuously differentiable, then there also exists $\overline{\phi }:(0,\infty )\to R$ such that $\phi =\overline{\phi }{|}_{[0,1]}$. We can then apply the above argument with Ostrowski's theorem to the function $\overline{\phi }$. In particular, there exists an open subset $U\subseteq (0,\infty )$ with $p^{\ast }\in U$ such that for any $p^0\in U$, we have $p^k\in U$ for iterates $p^k=\overline{\phi }\left(p^{k-1}\right)$ and ${lim}_{k\to \infty }{p}^k=p^{\ast }$. This also applies to any $p^0\in U\cap [0,1]$.

Now consider the actual update rule $\tilde{\phi }$ with iterates ${\tilde{p}}^k=\tilde{\phi }\left({\tilde{p}}^{k-1}\right)$ and ${\tilde{p}}^0=p^0\in (0,1]$. Let $k:=inf\{k\mid p^k\in (1,\infty \left)\right\}$; i.e., this is the smallest $k$ such that an iterate is out of bounds and thus $p^k\ne {\tilde{p}}^k$. If $k=\infty$, then we are done. Otherwise, we have ${\tilde{p}}^k=\tilde{\phi }\left(p^{k-1}\right)=1=p^{\ast }$, so the actual update rule $\tilde{\phi }$ also converges to its fixed point $p^{\ast }$ (potentially faster than $\overline{\phi }$). This concludes the proof.

Appendix B. Proof of Proposition 11

We will use a version of the strong law of large numbers for uncorrelated random variables with bounded variance, adapted from Neely (2021, Theorem 2).

Theorem 17. Let $\{X_t{\}}_{t\in N_0}$ be a sequence of pairwise uncorrelated random variables with mean $0$ and bounded variances. I.e., assume that

$E\left[X_t\right]=0$ for all $t\in N_0$

There exists $c>0$ such that $Var\left(X_t\right)\le c$ for all $t\in N_0$

$Cov(X_t,X_{t^{\prime }})=0$ for all $t\ne t^{\prime }\in N_0$.

Then almost surely 

$$\underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^T{X}_t=0.$$

We will apply this law to random variables $X_t:=S(P_t^{\prime },Y_t)-S(P_t^{\prime },f(P_t\left)\right)$, where $P_t^{\prime }$ is either $P_t$ or $f\left(P_t\right)$.

First, by Proposition 10, $E\left[X_t\right]=E\left[S\right(P_t^{\prime },Y_t)-S(P_t^{\prime },f\left(P_t\right)\left)\right]=0$. Second, by assumption, 

$$\underset{t}{sup}Var\left(S\right(P_t^{\prime },f\left(P_t\right)\left)\right)<\infty .$$

Hence, also 

$$\underset{t}{sup}Var\left(S\right(P_t^{\prime },f\left(P_t\right)\left)\right)=\underset{t}{sup}Var\left(E\right[S(P_t^{\prime },f(P_t\left)\right)\mid P_t\left]\right)\le \underset{t}{sup}Var\left(S\right(P_t^{\prime },f\left(P_t\right)\left)\right)<\infty .$$

It follows that also ${sup}_{t}Var\left(X_t\right)<\infty$.

Third, we know that $Y_t$ is independent of $P_{t^{\prime }}$ and $Y_{t^{\prime }}$ for $t>t^{\prime }$, conditional on $P_t$. Moreover, $P_t^{\prime }$ is constant given $P_t$. Hence, given $P_t$, also $X_t=S(P_t^{\prime },Y_t)-S(P_t^{\prime },f(P_t\left)\right)$ is independent of $X_{t^{\prime }}$. Moreover, 

$$E[X_t\mid P_t]=E\left[S\right(P_t^{\prime },Y_t)-S(P_t^{\prime },f\left(P_t\right))\mid P_t]=S(P_t^{\prime },f(P_t\left)\right)-S(P_t^{\prime },f(P_t\left)\right)=0.$$

It follows for $t>t^{\prime }$ that 

$$Cov(X_t,X_{t^{\prime }})=E\left[X_t{X}_{t^{\prime }}\right]=E\left[E\right[X_t{X}_{t^{\prime }}\mid P_t\left]\right]=E\left[E\right[X_t\mid P_t\left]E\right[X_{t^{\prime }}\mid P_t\left]\right]=0.$$

This shows all conditions of the theorem and thus shows that 

$$\underset{t\to \infty }{lim}\frac{1}{T}\sum _{t=1}^T{X}_t=0$$

almost surely.

Now we turn to the limit of $\frac{1}{T}{\sum }_{t=1}^{T}S(P_t^{\prime },f(P_t\left)\right)$. By assumption, ${sup}_t|S(P_t^{\prime },f(P_t\left)\right)|<\infty$, so this limit exists and is finite. Thus, almost surely 

$$\underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^{T}S(P_t^{\prime },f(P_t\left)\right)=\underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^{T}S(P_t^{\prime },Y_t)-X_t$$$$=\underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^{T}S(P_t^{\prime },Y_t)-\underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^T{X}_t=\underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^{T}S(P_t^{\prime },Y_t).$$

Using Proposition 10, it follows that almost surely 

$$\underset{T\to \infty }{lim}\frac{1}{T}Regret\left(T\right)=\underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^{T}S\left(f\right(P_t),Y_t)-S(P_t,Y_t)=\underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^{T}S\left(f\right(P_t),Y_t)-\underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^{T}S(P_t,Y_t)$$

 

$$=\underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^{T}S\left(f\right(P_t),f(P_t\left)\right)-\underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^{T}S(P_t,f(P_t\left)\right)=\underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^{T}S\left(f\right(P_t),f(P_t\left)\right)-S(P_t,f(P_t\left)\right).$$

Turning to the "in particular" part, note that this limit is finite by the above, and it is nonnegative since $S$ is assumed to be proper. Moreover, it follows that almost surely 

$$\underset{T\to \infty }{limsup}\frac{1}{T}Regret\left(T\right)=\underset{T\to \infty }{lim}\frac{1}{T}Regret\left(T\right)\ge 0.$$

 Thus, almost surely ${limsup}_{T\to \infty }\frac{1}{T}Regret\left(T\right)\le 0$ if and only if ${lim}_{T\to \infty }\frac{1}{T}{\sum }_{t=1}^{T}S\left(f\right(P_t),f(P_t\left)\right)-S(P_t,f(P_t\left)\right)=0.$ This concludes the proof.

Appendix C. Proof of Theorem 12

We begin by proving a lemma.

Lemma 18. Let $\phi ,\psi :N\to [0,\infty )$ and assume there exists a constant $C>0$ such that for all $t\in N,$ we have $\psi \left(t\right)\le C.$ Assume that for any $ϵ>0$, there exists $\delta >0$ such that if $\psi \left(t\right)>ϵ$ for any $t\in N$, then $\phi \left(t\right)>\delta$. Then 

$$\underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^T\phi \left(t\right)=0\Rightarrow \underset{T\to \infty }{lim}\frac{1}{T}\sum _{t=1}^T\psi \left(T\right)=0.$$

Proof. We prove the contrapositive. That is, we assume that there exists some constant $c>0$ such that there are infinitely many $T\in N$ such that $\frac{1}{T}{\sum }_{t=1}^T\psi \left(T\right)>c$. Let $T$ be the set of such $T$. We show that then there exists a constant $c^{\prime }>0$ such that for infinitely many $T$, $\frac{1}{T}{\sum }_{t=1}^T\phi \left(T\right)>c^{\prime }$.

Let $T\in T$. Since by assumption $\frac{1}{T}{\sum }_{t=1}^T\psi \left(T\right)>c,$ it follows that ${\sum }_{t=1}^T\frac{\psi \left(T\right)}{c}>T.$ Let $C^{\prime }:=max\{C,1/c\}+1$. Since $\psi \left(T\right)<C^{\prime }$ it must be $\psi \left(T\right)>\frac{c}{2C}$ for more than $\frac{c}{2C}$ fraction of the times $t\le T$. Otherwise, it would be 

$$\sum _{t=1}^T\frac{\psi \left(T\right)}{c}\le T(\frac{C}{c}\frac{c}{2C}+(1-\frac{c}{2C})\frac{ϵ}{2C})\le T(\frac{1}{2}+\frac{ϵ}{2C})<T.$$

By assumption, this gives us a $\delta >0$ such that whenever $\psi \left(T\right)>ϵ:=\frac{c}{2C}$, also $\phi \left(T\right)>\delta$. In particular, this applies to at least $ϵ$ fraction of $t\le T$. Hence, it follows that for any $T\in T$, 

$$\sum _{t=1}^T\phi \left(t\right)\ge \delta ϵT.$$

 This shows that there are infinitely many $T$ such that $\frac{1}{T}{\sum }_{t=1}^T\phi \left(t\right)>\delta ϵ$ and thus concludes the proof. ◻

Now we turn to the main proof.

Proof of Theorem 12. Let $(P_t{)}_t$ be the sequence of the agent's predictions. Assume $S$ is strictly proper, assume that ${sup}_{t}Var\left(S\right(P_t^{\prime },Y_t\left)\right)<\infty$ for $P_t^{\prime }\in \{P_t,f(P_t\left)\right\},$ and assume that there exists a compact set $C\subseteq [0,1]$ such that $P_t\in C$ for all $t$, and $S(p,f(p\left)\right),$ $S\left(f\right(p),f(p\left)\right),$ and $f\left(p\right)$ are continuous in $p$ at any $p\in C$.

To begin, note that continuity of $S(p,f(p\left)\right)$ and $S\left(f\right(p),f(p\left)\right)$ implies that both are also bounded on $C$ and thus ${sup}_t|S(P_t^{\prime },f(P_t\left)\right)|<\infty$ for $P_t^{\prime }\in \{P_t,f(P_t\left)\right\}$. Hence, by our assumptions, the conditions for Proposition 11 are satisfied.

"$\Rightarrow$". Assume $Regret\left(T\right)$ is sublinear. We want to show that then ${\sum }_{t=1}^T|f\left(P_t\right)-P_t|$ is sublinear. To do this, we will apply Lemma 18.

To begin, define $\phi \left(t\right):=S\left(f\right(P_t),f(P_t\left)\right)-S(P_t,f(P_t\left)\right)$ and note that $\phi \left(t\right)\ge 0$ since $S$ is proper. By Proposition 11, it follows that if $Regret\left(T\right)$ is sublinear, also ${\sum }_{t=1}^T\phi \left(t\right)$ is sublinear almost surely. For brevity, we omit the "almost surely" qualification in the following.

Next, define $\psi \left(t\right):=|f\left(P_t\right)-P_t|$, and note that $0\le \psi \left(t\right)\le 1$. Next, let $ϵ>0$ arbitrary. To apply Lemma 18 to $\phi$ and $\psi$, it remains to show that there exists $\delta >0$ such that whenever $\psi \left(t\right)\ge ϵ$, then $\phi \left(t\right)\ge \delta$.

To that end, let 

$$\delta :=\underset{\{p\in C\mid |p-f(p)|\ge ϵ\}}{min}S\left(f\right(p),f(p\left)\right)-S(p,f(p\left)\right).$$

 Since $f$ is continuous for any $p\in C$, the set $\{p\in C\mid |p-f(p)|\ge ϵ\}$ is compact. Moreover, $S\left(f\right(p),f(p\left)\right)$ and $S(p,f(p\left)\right)$ are continuous by assumption, and thus the minimum is attained at some point $\hat{p}\in C$. But since $S$ is strictly proper, it follows $\delta =S\left(f\right(\hat{p}),f(\hat{p}\left)\right)-S(\hat{p},f(\hat{p}\left)\right)>0.$ Hence, since $P_t\in C$ for any $t\in N,$ it follows that whenever $\phi \left(t\right)\ge ϵ,$ it follows

$$\phi \left(t\right)=S\left(f\right(P_t),f(P_t\left)\right)-S(P_t,f(P_t\left)\right)\ge \delta .$$

This shows all conditions for Lemma 18. Hence, we conclude that ${lim}_{t\to \infty }\frac{1}{T}{\sum }_{t=1}^T|f\left(P_t\right)-P_t|=0$.

"$\Leftarrow$". Let $\phi \left(t\right):=|f\left(P_t\right)-P_t|$ and $\psi :=S\left(f\right(P_t),f(P_t\left)\right)-S(P_t,f(P_t\left)\right)$. We assume that ${\sum }_{t=1}^T\phi \left(t\right)$ is sublinear in $T$ and want to show that then $Regret\left(T\right)$ is sublinear as well. To do so, we will show that ${\sum }_{t=1}^T\psi \left(t\right)$ is sublinear using our lemma, and then the required statement follows again from Proposition 11.

Now we have to show the conditions of the lemma. First, as before, $\phi \left(t\right)\ge 0$ and $\psi \left(t\right)\ge 0.$ Second, as noted in the beginning, we have ${sup}_t\psi \left(t\right)<\infty$ by our assumption that $S\left(f\right(p),f(p\left)\right)$ and $S(p,f(p\left)\right)$ are continuous on $C.$ Now let $ϵ>0$ arbitrary. Assume that $S\left(f\right(P_t),f(P_t\left)\right)-S(P_t,f(P_t\left)\right)>ϵ$ for some $ϵ>0$ and $t\in N.$

Consider the set $C^{\prime }:=\{p\in C\mid S(f\left(p\right),f\left(p\right))-S(p,f\left(p\right))\ge ϵ\}$. Since $S\left(f\right(p),f(p\left)\right)$ and $S(p,f(p\left)\right)$ are continuous on $C$ by assumption, this set is compact. Moreover, the function $p\in C\mapsto |p-f\left(p\right)|$ is continuous since $f$ is continuous on $C$ by assumption. Hence, the minimum $\delta :={min}_{p\in C^{\prime }}|p-f\left(p\right)|$ is attained at some point $\hat{p}\in C^{\prime }.$

Now, if $\delta =0,$ we would have $\hat{p}=f\left(\hat{p}\right)$ and thus 

$$S\left(f\right(\hat{p}),f(\hat{p}\left)\right)-S(\hat{p},f(\hat{p}\left)\right)=S(\hat{p},\hat{p})-S(\hat{p},\hat{p})=0<ϵ,$$

 which is a contradiction. Hence, $\delta >0.$ Since $P_t\in C,$ it follows from $S\left(f\right(P_t),f(P_t\left)\right)-S(P_t,f(P_t\left)\right)\ge ϵ,$ for $t\in N$ that $|P_t-f\left(P_t\right)|\ge \delta .$ This shows the third condition for the lemma. We can thus conclude that ${lim}_{T\to \infty }\frac{1}{T}{\sum }_{t=1}^T\psi \left(t\right)=0.$ Using Proposition 11, this concludes the proof. ◻

Appendix D. Armstrong's backwards-facing oracle

Here, we analyze a version of Armstrong (2018) [AF · GW]'s backwards-facing oracle. This is a version of the online learning setup from Section 5 in which the agent’s prediction $P_{t+1}$ is trained to minimize the average historical loss,

$$L_t\left(p\right):=\frac{1}{t}\sum _{t^{\prime }=1}^t-S(p,Y_{t^{\prime }}).$$

We consider training via gradient descent and let $P_{t+1}=\Pi (P_t-\alpha {\nabla }_p{L}_t(P_t\left)\right)$ for some learning rate $\alpha .$

In the following, we show that, if this learning scheme converges to a point $p^{\ast }\in (0,1),$ then ${\nabla }_p\left(S\right(p^{\ast },\perp f\left(p^{\ast }\right)\left)\right)=0.$ Afterwards, we conclude from Proposition 7 that $p^{\ast }$ must be a fixed point (assuming that $g^{\prime }\left(p^{\ast }\right)\ne 0$).

 Proposition 19. Assume $P_{t+1}=\Pi (P_t-\alpha {\nabla }_p{L}_t(P_t\left)\right)$ for $t\in N$ are the agents predictions and ${lim}_{t\to \infty }{P}_t=p^{\ast }$ almost surely for some $p^{\ast }\in (0,1).$ Assume that $f$ is continuous and that ${\partial }_{1}S(p,y)$ exists and is continuous for any $p\in (0,1)$ and $y\in \{0,1\}$. Then ${\nabla }_p\left(S\right(p^{\ast },\perp f\left(p^{\ast }\right)\left)\right)=0.$

Proof. To begin, note that since $p^{\ast }\in (0,1)$ we can choose a closed interval $I\subseteq (0,1)$ such that $p^{\ast }\in int\left(I\right)$. By assumption, ${\partial }_{1}S(p,y)$ is continuous and thus bounded for $p\in I,y\in \{0,1\}$. For each $t$, let $Q_t$ be the projection of $P_t$ onto $I$. Finally, let $L\left(p\right)=-S(p,f(p^{\ast }\left)\right)$.

We will show the following:

1. $E\left[\nabla L_t\right(Q_t\left)\right]\to 0$ as $t\to \infty$
2. for all $p\in (0,1)$, $E\left[\nabla L_t\right(p\left)\right]\to \nabla L\left(p\right)$ as $t\to \infty$
3. $E\left[\nabla L_t\right(Q_t\left)\right]\to \nabla L\left(p^{\ast }\right)$ as $t\to \infty$

from which it follows that $\nabla L\left(p^{\ast }\right)=0$.

1. “$E\left[\nabla L_t\right(Q_t\left)\right]\to 0$ as $t\to \infty$”. Note that there almost surely exists some $T$ such that $P_t\in (0,1)$ and thus also $\nabla L_t\left(P_t\right)=\frac{P_{t+1}-P_t}{\alpha }$ for all $t\ge T.$ Since $P_t\stackrel{\text{a.s.}}{\to }{p}^{\ast }$ as $t\to \infty ,$ it follows that $\nabla L_t\left(P_t\right)\stackrel{\text{a.s.}}{\to }0$ as $t\to \infty$. Moreover, we have that almost surely $P_t\in I$ for $t$ sufficiently large, so that almost surely $P_t=Q_t$ and $\nabla L_t\left(P_t\right)=\nabla L_t\left(Q_t\right)$ for $t$ sufficiently large. Thus, almost surely, 

$$\underset{t\to \infty }{lim}\nabla L_t\left(Q_t\right)=\underset{t\to \infty }{lim}\nabla L_t\left(P_t\right)=0.$$

Finally, since $\nabla L_t\left(Q_t\right)$ is bounded, we have by the dominated convergence theorem that $\nabla L_t\left(Q_t\right)\stackrel{L^1}{\to }0$ and as a consequence,

$$\underset{t\to \infty }{lim}E\left[\nabla L_t\right(Q_t\left)\right]=0.$$

2. “for all $p\in (0,1)$, $E\left[\nabla L_t\right(p\left)\right]\to \nabla L\left(p\right)$ as $t\to \infty$”. We have that 

$$\begin{array}{cc}E\left[\nabla L_t\right(p\left)\right]& =-\frac{1}{t}\sum _{t^{\prime }=1}^{t}E\left[{\partial }_{1}S\right(p,Y_{t^{\prime }}\left)\right]=-\frac{1}{t}\sum _{t^{\prime }=1}^{t}E\left[E\left[{\partial }_{1}S\right(p,Y_{t^{\prime }}\left)\right|P_{t^{\prime }}]\right]\\ & =-\frac{1}{t}\sum _{t^{\prime }=1}^{t}E\left[\right(1-f\left(P_{t^{\prime }}\right)\left){\partial }_{1}S\right(p,0)+f(P_{t^{\prime }}\left){\partial }_{1}S\right(p,1\left)\right]\\ & =-(1-\frac{{\sum }_{t}Ef\left(P_{t^{\prime }}\right)}{t}){\partial }_{1}S(p,0)-\frac{{\sum }_{t}Ef\left(P_{t^{\prime }}\right)}{t}{\partial }_{1}S(p,1)\end{array}$$

Since $f$ is continuous, we have $f\left(P_t\right)\stackrel{\text{a.s.}}{\to }f\left(p^{\ast }\right)$. Then, by compactness, we have that $f$ is bounded on $[0,1]$. Finally, by the dominated convergence theorem, we may conclude $Ef\left(P_t\right)\to f\left(p^{\ast }\right)$ as $t\to \infty$. As a consequence, $\frac{1}{t}{\sum }_{t^{\prime }\le t}Ef\left(P_{t^{\prime }}\right)\to f\left(p^{\ast }\right)$ as $t\to \infty$.

Thus, 

$$\underset{t\to \infty }{lim}E\left[\nabla L_t\right(p\left)\right]=-(1-f(p^{\ast }\left)\right){\partial }_{1}S(p,0)-f\left(p^{\ast }\right){\partial }_{1}S(p,1)=-{\partial }_{1}S(p,f(p^{\ast }\left)\right)=\nabla L\left(p\right)$$

3. “$E\left[\nabla L_t\right(Q_t\left)\right]\to \nabla L\left(p^{\ast }\right)$ as $t\to \infty$”. Note that 

$$|\nabla L_t\left(Q_t\right)-\nabla L_t\left(p^{\ast }\right)|\le \underset{y}{max}\left|{\partial }_{1}S\right(Q_t,y)-{\partial }_{1}S(p^{\ast },y\left)\right|\stackrel{\text{a.s.}}{\to }0$$

as $t\to \infty$, since ${\partial }_{1}S(p,1)$ and ${\partial }_{1}S(p,0)$ are both continuous functions of $p$ on $I$.

Finally, by the dominated convergence theorem and our second result,

$$\underset{t\to \infty }{lim}E\left[\nabla L_t\right(Q_t\left)\right]=\underset{t\to \infty }{lim}E\left[\nabla L_t\right(p^{\ast }\left)\right]=\nabla L\left(p^{\ast }\right).$$

And we are done. ◻

Corollary 20. Assume $S$ is proper and let $G,g$ as in the Gneiting and Raftery characterization (Theorem 1) be continuously differentiable at any $p\in (0,1).$ Assume $f$ is continuous, $P_t$ as defined above converges to some prediction $p^{\ast }\in (0,1)$ almost surely, and $g^{\prime }\left(p^{\ast }\right)\ne 0.$ Then $p^{\ast }$ is a fixed point of $f$.

Proof. By Proposition 7, we have ${\partial }_{1}S(p,y)=g^{\prime }\left(p\right)(y-p)$ for any $y\in \{0,1\},p\in (0,1).$ Thus, since $G^{\prime \prime }=g^{\prime }$ is continuous by assumption, also ${\partial }_{1}S(p,y)$ is continuous. Hence, by Proposition 19, it follows that ${\nabla }_p\left(S\right(p^{\ast },\perp f\left(p^{\ast }\right)\left)\right)=0.$ By Proposition 7, it follows that $p^{\ast }$ is a fixed point of $f$. ◻

2 comments

Comments sorted by top scores.