Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity.
Aaron SidfordMengdi WangLin YangYinyu YePublished in: AISTATS (2020)
Keyphrases
- sample complexity
- two player games
- theoretical analysis
- special case
- upper bound
- lower bound
- learning problems
- supervised learning
- evaluation function
- learning algorithm
- active learning
- training examples
- generalization error
- sample size
- monte carlo
- combinatorial optimization
- model selection
- game tree
- small number
- markov decision processes
- np hard
- function approximation