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?


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.