An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap.
Yuanhao WangRuosong WangSham M. KakadePublished in: CoRR (2021)
Keyphrases
- lower bound
- upper bound
- markov decision processes
- vc dimension
- decision diagrams
- average case complexity
- constant factor
- objective function
- branch and bound algorithm
- reinforcement learning
- optimal solution
- branch and bound
- np hard
- factored mdps
- state space
- markov decision problems
- worst case
- finite state
- markov decision process
- lower and upper bounds
- planning under uncertainty
- sufficiently accurate
- linear programming relaxation
- concept class
- target function
- average cost
- probabilistic planning
- multi agent
- decision theoretic planning
- multi valued
- polynomial approximation
- semi markov decision processes