Given:
- a metric $d$
- an aggregate function $f$
- some sets (or multisets or random variables) $X$,$Y$
What do we call:
- $d(f(X),f(Y)) \leq f( [d(X_0,Y_0) \cdots d(X_n,Y_n)] )\ \forall\ k\in[0,1), X,Y$
- $d(f(X),f(Y))\leq \max_i d(X_i,Y_i)\ \forall X,Y$
Similar definitions:
$f$ is a contraction mapping: $d(f(x),f(y))\leq k\ d(x,y)\quad{}\forall x, y$
$f$ is subadditive: $f(x+y)\leq f(x)+f(y)\quad{}\forall x, y$
the similarity being two operations "commute" (but with inequality not equality).
Why
You can solve a Markov decision process for some "state reducer" and some "action reducer", two reducing operations each satisfying [2] (otherwise, the iterative algorithm has no proof of convergence). different pairs of "MDP reducers" (what i call "satisfying property 2") give us different solutions.
Examples
Expectation and maximum/minimum are "mdp reducers"
$|E[X] - E[Y]| \leq \max_i |X_i - Y_i|$
$|\max_i X_i - \max_i Y_i| \leq \max_i |X_i - Y_i|$
solving an mdp given mean for the state reducer and max for the action reducer answers "what's the best i can do in expectation?"
if i have a name for "mdp reducer", i can get a list of them, and play around with them, and find new interpretations i.e. answer different questions i.e. solve different problems.
does [1] have a name? does [2] have a name? if not, what are some functions that satisfy [2]?
(cross posted on mathoverflow)
