3 ms·
It's proven that if you want polynomial sample complexity in the size of the state space you need directed exploration. The algorithms 'flail' because they are
by eutectic 5y ago
It's proven that if you want polynomial sample complexity in the size of the state space you need directed exploration. The algorithms 'flail' because they are initialized with random policies.
- whimsicalism 5y agoCouldn't any directed exploration also be produced as the result of random flailing? Or is this average sample complexity?
- eutectic 5y agoAn example of a bad case for random exploration would be a narrow ridge where you die if you fall off and you only receive reward if you get to the end. So it's a worst case result with respect to the MDP, but expected time/high probability with wrt random chance.