The Tiger's Stripes


A blog on fun research and tools in computer science and game theory.

Author: Bo Waggoner RSS feed

Risk Aversion and Max-Entropy

Posted: 2016-10-02.

I want to share a nice little problem that came up in discussion between Yiling Chen, Madhu Sudan, and myself. It turns out to have a cute solution that connects the geometry of proper scoring rules with a "max-entropy" rule.

A primer on proper scoring rules will be useful first!


The Tale of Rita

Once upon a time, Risk-Averse Rita worked as a weather reporter in Incentiveland playing the following game each day:

  1. Rita is given a set $Q$ of possible probability distributions over the day's weather outcome, e.g. $Q \subseteq \Delta_{\{\text{rain, cloud, sun}\}}$.
  2. Rita makes a prediction $p$, a distribution over the day's weather outcome.
  3. Nature picks a true distribution $q$ from $Q$, perhaps adversarially depending on Rita's prediction.
  4. The true weather outcome $e$ is drawn according to $q$.
  5. Rita is scored with a proper scoring rule $S(p,e)$.

In the case where $|Q| = 1$, i.e. Rita knows the true distribution $q$ of nature, then properness of the scoring rule implies that she should just report $q$. Now, if Rita is risk averse and wishes to maximizes her minimum expected score, how should she play? In math, she wants to solve

\[ \max_p \min_{q \in Q} \mathbb{E}_{e\sim q} S(p, e) . \] Recalling the notation $S(p;q)$ for expected score of report $p$ when $e \sim q$, this is \[ \max_p \min_{q \in Q} S(p;q) . \]

The Solution

Luckily, Rita found an optimal strategy. The intuitive statement of the solution is:

If $Q$ is a convex set, then the optimal strategy is to assume the adversary will pick the "max-entropy" distribution in $Q$ and best-respond accordingly.

Furthermore, in this case, the adversary cannot improve on actually picking the "max-entropy" distribution.

Why do I have quotes around "max-entropy"? Because the measure of entropy changes depending on the scoring rule.

If you read my post on generalized entropies, you know that:

  1. Every proper scoring rule maps to a convex function $G$ where $G(q)$ is the expected score for optimally (truthfully) reporting given belief $q$.
  2. The concave function $F = -G$ can be interpreted as a "generalized entropy" function under an axiomatic approach.
For example, the log scoring rule is $S(p,e) = \log p(e)$, so its expected truthful score function is $\sum_e p(e) \log p(e) = -H(p)$, so its corresponding generalized entropy is just Shannon entropy. For another example, the quadratic scoring rule is $S(p,e) = 2p(e) - \sum_{e'} p(e')^2$ and has corresponding $G(p) = \sum_e p(e)^2$, or generalized entropy $-\|p\|_2^2$, i.e. the collision probability.

Theorem. Let $Q$ be any convex set of distributions and suppose Rita faces scoring rule $S$ with differentiable convex expected score $G$. To solve the problem \[ \arg\max_p \min_{q \in Q} S(p;q) , \] Rita's optimal strategy is to report \[ q^* := \arg\min_{q \in Q} G(Q) . \]

Proof. It may be helpful to first see the pictures below. First, we will show that if Rita picks $p=q^*$, then her expected score is at least $G(q^*)$ for any choice of nature (achieved when nature chooses $q^*$). Then, we will show that any other report $p \neq q^*$ results in a worse score.

Claim 1. $\min_{q\in Q} S(q^*;q) = G(q^*)$.

Proof of claim: We just want to show for all $q \in Q$ \begin{align} S(q^*; q) - G(q^*) &\geq 0 \\ \iff ~ \langle dG(q^*), q-q^* \rangle &\geq 0 \end{align} using the scoring rule characterization $S(p;q) = G(p) + \langle dG(p), q-p \rangle$ where $dG(p)$ is the subgradient (i.e. gradient) of $G$ at point $p$.

Now we just want to prove $\langle dG(q^*), q-q^* \rangle \geq 0$ for all $q \in Q$. But since $G$ is differentiable, this is actually equal to the directional derivative of $G$ in the direction $q-q^*$: \[ \langle dG(q^*), q-q^* \rangle = \lim_{h\to 0} \frac{G(q^* + h(q-q^*)) - G(q^*)}{h} . \] Now, we assumed $Q$ is a convex set, and both $q^*,q \in Q$. So for every $0 \leq h \leq 1$, the point $q' := q^* + h(q-q^*)$ is in $Q$. Furthermore, since we assumed $q^* = \arg\min_{p \in Q} G(p)$, we have $G(q') - G(q) \geq 0$.

So the right side is a limit over nonnegative terms, so the left side cannot be negative.

Claim 2. For all $p$, $\min_{q \in Q} S(p;q) \leq G(q^*)$.

Proof of claim: In particular, $\min_{q \in Q} \leq S(p;q^*)$ because $q^* \in Q$. Now by definition of a proper scoring rule, $S(p;q^*) \leq S(q^*;q^*) = G(q^*)$.

Here we have a binary outcome problem, e.g. the weather is either sunny or not, with probability of sun on the horizontal axis. Plots the convex expected score function $G$ for a scoring rule $S$, and the convex set $Q$ of possible probability distributions of nature.

a convex G and convex set Q for binary outcome

Above: $q^*$ is the "max-entropy" (minimum $G(q)$) among the set $Q$. I claim Rita should pick $q^*$.

Below: Illustration of Claim 1. Supposing Rita reports $q^*$, then nature's best response is $q^*$, as any other choice $q \in Q$ results in a higher expected score $S(q^*;q)$. This shows Rita can achieve $G(q^*)$ by picking $q^*$.

a convex G and convex set Q for binary outcome

Below: Illustration of Claim 2. If Rita makes any other prediction $p \neq q^*$, nature can force her to achieve worse than $G(q^*)$ by picking $q^*$.

a convex G and convex set Q for binary outcome

Below: By flipping $G$, we can view it as a generalized entropy $F$ where $q^*$ is the max-entropy distribution in $Q$.

a convex G and convex set Q for binary outcome

Questions

Here are some exercises you might enjoy followed by open questions that would be nice to resolve, at least for Rita's sake.

Exercise 1.
Rita's cousin, Risk-Neutral Rick, has a "meta-belief" in the form of a distribution $r$ over $Q$, i.e. $r$ assigns a probability to each $q \in Q$ as being the correct belief. How should Rick report to maximize expected score, i.e. what $p$ solves

\[ \max_p \mathbb{E}_{q \sim r} \mathbb{E}_{e \sim q} S(p, e) ~ ? \]

Exercise 2.
Suppose $Q$ is not a convex set; give a counterexample to the theorem.

Open question 1.
Suppose $Q$ is not a convex set. I would guess that Rita's optimal report is the max-entropy $q$ in the convex hull of $Q$. Prove me right, or disprove it and find Rita's optimal strategy instead.

Open question 2.
What if $G$ is convex, but not differentiable?
The theorem probably still holds, but the proof needs to be much more careful. What happens when $G$ is non-differentiable is that, at some points $q$, there are multiple choices of subgradient $dG(q)$. If we use the wrong one when constructing the scoring rule $S$, then the theorem won't hold; to see this, picture $G$ with a kink at its minimum (such as $G(x) = |x|$) and convince yourself that, if $Q$ contains a ball around the global minimum, then the subgradient chosen at the minimum must be $0$ for the theorem to hold. Maybe elsewhere you don't need to be so careful, and can just use that the subgradients at $p$ form a convex set; I'm not sure.

Open question / challenge 3.
Extend this theorem, as far as possible, to the case of general decision problems rather than just proper scoring rules.


Comments


Post a comment:
Sentient beings: Ignore the following two fields.

Name:


Limits to 1000 characters. HTML does not work but LaTeX does, e.g. $\$$x^y$\$$ displays as $x^y$.
Please allow a few seconds after clicking "Submit" for it to go through.