Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions.
Gellért WeiszPhilip AmortilaCsaba SzepesváriPublished in: ALT (2021)
Keyphrases
- lower bound
- decision diagrams
- planning problems
- markov decision processes
- initial state
- dynamic programming
- reinforcement learning
- stochastic domains
- worst case
- decision theoretic planning
- upper bound
- optimal cost
- state space
- optimal solution
- optimal planning
- probabilistic planning
- heuristic search
- action sets
- np hard
- discounted reward
- action selection
- average cost
- planning under uncertainty
- markov decision problems
- optimal plans
- partially observable
- target function
- finite horizon
- ai planning
- decision theoretic
- optimal policy
- min sum
- average case complexity
- derived predicates
- planning domains
- efficient computation
- total cost
- domain independent
- basis functions
- objective function