CS7642_Week5 Flashcards
What does Dr. Littman suggest is the fundamental difference between RL and other kinds of machine learning?
Exploration
True/False: Gittin’s index is a good way of calculating whether to make an exploration decision or not?
False (unless you’re working with K-armed bandit problems - otherwise research has shown it generally doesn’t work well).
What happens to Hoeffding bounds as we have more data to sample from?
The bounds get SMALLER (i.e. we’re more confident in our estimate). This is because the bounds shrink with the square root of ‘n’ samples.
What is the ‘Simulation Lemma’?
The idea that if we have a “pretty good” estimate of the real MDP, then optimizing our rewards in that estimate is going to be pretty good in the real MDP
What is the ‘Explore or Exploit’ Lemma?
If all transitions are either accurately estimated or unknown, then the optimal policy is either near optimal OR an unknown state is reached “quickly”
What is the RMax algorithm?
“Optimism in the face of uncertainty”. In essence, it says that anytime we don’t know something, assume it’s awesome, and behave accordingly. Eventually we’ll have traversed the unknown edges of the MDP and be left with an optimal policy.
Algorithm:
- Keep track of the MDP
- Any unknown state-action pair is defined as “Rmax”
- Solve the MDP
- Take action from it
Rmax is an efficient algorithm for deterministic MDPs? (True/False)
True. Can be solved in polynomial time.
Why are Hoeffding bounds important?
They help us with epistemological uncertainty. In decision making, we’re often uncertain about what we know. Hoeffding bounds tell us how certain we actually are.
