Optimistic planning in Markov decision processes using a generative model
We consider the problem of online planning in a Markov decision process with discounted rewards for any given initial state. We consider the PAC sample complexity problem of computing, with probability 1−δ, an �-optimal action using the smallest possible number of calls to the generative model (which provides reward and next-state samples). We design an algorithm, called StOP (for StochasticOptimistic Planning), based on the "optimism in the face of uncertainty" principle. StOP can be used in the general setting, requires only a generative model, and enjoys a complexity bound that only depends on the local structure of the MDP.
The paper considers the problem of online planning in a MDP with discountedrewards. More precisely, the problem is, for any given initial state, to decide an action (at the initial state) that is epsilon-optimal with high probability.The algorithm is assumed to have access to the generative model, i.e.,an oracle that, when invoked with a state-action pair, provides a reward anda next-state according to the probability distributions associated with thetarget MDP. The paper designs an algorithm called StOP with sample complexitynearly as small as the best baseline algorithm OP-MDP, which is assumed tohave access to the true distributions over rewards and next-states. Thus,the advantage of StOP is obvious.The sample complexity of StOP derived depends on a parameter kappa, which isa complexity measure of the target MDP. Intuitively, kappa measures hardnessof approximating the optimal reward using random rollouts in the look-ahead(action-transition) tree.The paper is well-motivated and clearly written. The sample complexity boundderived is good. It seems that the idea behind the algorithm is a reductionto the best-arm identification, which is a standard way of estimating the gamevalue by random playouts in the game tree (c.f. UCT). So it should beclarified what is the technical contribution and what is the key to derivingthe small sample complexity.Some specific comments:It is unclear how the authors derive from Theorem 3 the sample complexityin terms of kappa given in Introduction. Indeed, kappa is not defined inthe body of the paper.It would be helpful to give intuitions about the meanings of kappa and/orS^{epsilon,*}. It is important to characterize (or upperbound) the kappain terms of some simpler and combinatorial measures of MDP, and therebyto make it clear what structures of MDPs make the proposed method effective.