3 problems

Let $cDim$ be the dimension of the tabular state space. In the upper bound for plug-in value-function estimation, a factor $clog cDim$ multiplies the dependence on the span semi-no…

Span-dependent plug-in lower-bound conjecture. There is a Markov reward process for which this bound holds. The claim would show that the corresponding upper bound is sharp up to a…

Let $cM_{cmathsf{var}}(csigvalbd,csigrewbd)$, $cM_{cmathsf{vfun}}(cvalbd,csigrewbd)$, and $cM_{cmathsf{rew}}(crmax,csigrewbd)$ denote the classes of Markov reward processes with, r…