given
a metric $d$
an aggregate function $f$
some sets (or multisets or random variables) $X$,$Y$
what do we call:
[1] $d(f(X),f(Y)) \leq f( [d(X_0,Y_0) ... d(X_n,Y_n)] )\ \forall\ k\in[0,1), X,Y$
[2] $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)\ \forall x, y$
$f$ is subadditive := $f(x+y)\leq f(x)+f(y)\ \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 math.stackexchange)
