Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions.
Gellért WeiszPhilip AmortilaCsaba SzepesváriPublished in: CoRR (2020)
Keyphrases
- lower bound
- initial state
- dynamic programming
- markov decision processes
- worst case
- decision diagrams
- optimal solution
- action sets
- stochastic domains
- planning problems
- optimal cost
- optimal planning
- vc dimension
- upper bound
- reinforcement learning
- decision theoretic planning
- optimal plans
- discounted reward
- derived predicates
- action selection
- average cost
- state space
- objective function
- partially observable
- planning under uncertainty
- finite horizon
- finite state
- optimal policy
- search algorithm
- blocks world
- min sum
- optimal control
- average case complexity