0
$\begingroup$

Consider $$ R =\sup_{f\in\mathcal{F}} \left[ \frac{1}{n}\sum_{i=1}^n f(X_i) - \mathbb{E}[f(X)] \right] $$ If $X_i$'s are i.i.d., then uniform law of large number shows that, if $\mathcal{F}$ is well-behaved, then $R=O(1/\sqrt{n})$ with high probability.

There are similar results for the case: $X_i$'s are Non-i.i.d. but mixing process.

I wonder if there are similar results in a MDP setting: Let $\pi$ be a policy (map state to action). If fix $\pi$, then state $x_i$ forms a Markov chain. With some mixing arguments, for any starting state $x_1$, we have $$ r = \frac{1}{n}\sum_{i=1}^n f^\pi(x_i) - \mathbb{E}_{x}[f^\pi(x)] $$ is $O(1/\sqrt{n})$ with high probability, where the expectation is taken over the limiting distribution of state $x$.

Is there some uniform version of this?

$$ R =\sup_{\pi\in\mathcal{F}, x_1} \left[ \frac{1}{n}\sum_{i=1}^n f^\pi(x_i) - \mathbb{E}_{x}[f^\pi(x)] \right] $$ Can we say if the policy family $\mathcal{F}$ is well-conditioned (maybe the the underline MDP is also simple in some sense), we have $R=O(1/\sqrt{n})$ with high probability?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.