New Paper: Infra-Bayesian Decision-Estimation Theory

Alright, as I've mentioned before [LW(p) · GW(p)] I'm terrible at abstract thinking, so I went through the post and came up with a concrete example. Does this seem about right?

We are running a quantitative trading firm, we care about the closing prices of the S&P 500 stocks. We have a forecasting system which is designed in a robust, "prediction market" style. Instead of having each model output a single precise forecast, each model $M^j(\text{for}j=1,\dots ,k)$

 outputs a set of probability distributions over tomorrow’s closing prices. That is, for each action $a$ (for example, “buy” or “sell” a particular stock, or more generally “execute a trade decision”), our model returns a set

$Mj\left(a\right)\subseteq \Delta \left(FuturePrices\right),M^j\left(a\right)\subseteq \Delta \left(\text{Future Prices}\right),$

which means that $M^j\left(a\right)$ is a nonempty, convex set of probability distributions over outcomes.

This definition allows "nature" (the market) to choose the distribution that actually occurs from within the set provided by our model. In our robust framework, we assume that the market might select the worst-case distribution in $M^j\left(a\right)$. In other words, our multivalued model is a function

$M:A\to \square \left(O\right),M:A\to \square \left(O\right),$

with $\square \left(O\right)$ representing the collection of sets of probability distributions over outcomes. Instead of pinning down exactly what tomorrow’s price will be if we take a particular action, each model provides us a “menu” of plausible distributions over possible closing prices.

We do this because there is some hidden-to-us world state that we cannot measure directly, and this state might even be controlled adversarially by market forces. Instead of trying to infer or estimate the exact hidden state, we posit that there are a finite number of plausible candidates for what this hidden state might be. For each candidate hidden state, we associate one probability distribution over the closing prices. Thus, when we look at the model for an action, rather than outputting a single forecast, the model gives us a “menu” of distributions, each corresponding to one possible hidden state scenario. In this way, we deliberately refrain from committing to a single prediction about the hidden state, thereby preparing for a worst-case (or adversarial) realization.

Given a bettor $B$, MDP $M$ and policy $\pi$ we define ${\text{bet}}_{M,\pi }^B:\left(\right[0,1]\times (\text{states}\times \text{acts}\times [0,1]{)}^{\left[H\right]})\to R$, the aggregate betting function, as
${\text{bet}}_{M,\pi }^B(r_0,s_1,a_1,...r_H):=1+{\sum }_{h=0}^H\left({\text{lbet}}_{M,\pi }^{B,h,s_h,a_h}\right(r_h,s_{h+1},a_{h+1})-1)$
Where $t{r}_t$ and ${\pi }_t$ are the trajectory in episode $t$ and policy in episode $t$, respectively.

Next, our trading system aggregates these imprecise forecasts via a prediction-market-like mechanism. Inside our algorithm we maintain a collection of “bettors”. Each "bettor" (besides the pessimistic and uniform bettors, which do the obvious thing their names imply) corresponds to one of our underlying models (or to aspects of a model). Each bettor $B$ is associated with its own preferred prediction (derived from its hypothesis set) and a current “wealth” (i.e. credibility). Instead of simply choosing one model, every bettor places a bet based on (?)how well our market prediction aligns with its own view(?),

$\text{Robust Universal Estimator (RUE)}$
$\text{Parameters:}\text{Hypothesis class}H,\text{rounds}T,\text{reward function}r,\text{prior}{\zeta }_1$

$ϵ\leftarrow min(\frac{1}{2},\sqrt{\frac{\ln \left(2\right)}{T}})$

$\text{Function estimate(}\zeta \text{,}a\text{):}$

$return\underset{\mu \in \Delta O}{\text{argmin}}\underset{B\sim \zeta }{E}[\text{if}B\ne \bullet ,2D_H^2(\mu \to M_B\left(a\right)),\text{else}\epsilon \cdot \underset{o\sim \mu }{E}\left[r\right(a,o\left)\right]]$

$\text{Function update(}\zeta \text{,}\overline{M}\text{,}a\text{,}o\text{):}$

$forB\in H\cup \left\{u\right\}:$

${\mu }_B\leftarrow {\text{argmin}}_{\mu \in M_B\left(a\right)}{D}_H^2\left(\overline{M}\right(a),\mu )$

$\xi \left(B\right)\leftarrow \zeta \left(B\right)\cdot (\sqrt{\frac{{\mu }_B\left(o\right)}{\overline{M}\left(a\right)\left(o\right)}}+D_H^2(\overline{M}\left(a\right)\to M_B\left(a\right)\left)\right)$

$\xi (\bullet )\leftarrow \zeta (\bullet )\cdot (1+\epsilon (E_{o^{\prime }\sim \overline{M}\left(a\right)}\left[r\right(a,o^{\prime }\left)\right]-r(a,o)\left)\right)$

$\text{return}\xi$

$\text{for}1\le t\le T:$

${\hat{M}}_t\leftarrow \lambda a.\text{estimate}({\zeta }_t,a)$

$\text{return}{\hat{M}}_t$

$\text{Receive}{a}_t,o_t\text{from the environment}$

${\zeta }_{t+1}\leftarrow \text{update}({\zeta }_t,{\hat{M}}_t,a_t,o_t)$
$\text{end}$

To calculate our market prediction $\hat{M}$, we solve a convex minimization problem that balances the differing opinions of all our bettors (weighted by their current wealth $\zeta$) in such a way that it (?)minimizes their expected value on update(?).

The key thing here is that we separate the predictable / non-adversarial parts of our environment from the possibly-adversarial ones, and so our market prediction $\hat{M}$ reflects our best estimate of the outcomes of our actions if the parts of the universe we don't observer are out to get us.

Is this a reasonable interpretation? If so, I'm pretty interested to see where you go with this. 

Congratulations on this paper. It seems like a major result. 

Any chance of more exposition for those of us less cognitively-inclined? =)