During the first episode, it's 100% exploration, because all our Q values are 0. Suppose we have 1000 time steps, and it's terminated by meeting a reward. So, after the first episode, why can't we make it 100% exploitation? Why do we still need exploration?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
You can't guarantee that you have taken every action from every state, even with 1000 time steps. There would be multiple outcomes:
The episode terminates, either by success or failure before the 1000 time steps. The agent is trying to maximise reward, if this is achieved by taking less than 1000 steps then it will do. It won't just walk around until it hits an arbitrary number of time steps.
If you have more states than time steps then you will never be unable to visit all states and so you cannot guarantee that the policy you followed was optimal (and hence would still want to explore). Even if you have #states = #time-steps then you will almost certaintly have more state-action pairs than timesteps. The only time this would be equal is if from every state there is only one action, which would be a trivial problem that wouldn't need RL to solve.
-
$\begingroup$ Ok this makes sense, it’s more like since we’re not sure it has taken every action possible from every state , we can’t rely on the Q values as they might not be correct, ok suppose we do 2000 episodes or more, can we now make it 100% exploitation $\endgroup$– ChukwudiJun 16, 2020 at 15:17
-
$\begingroup$ Our estimated Q values will asymptotically approach the optimal Q values (Q^* in most textbooks) as the number of episodes approaches infinite. The exact number of episodes would be a function of the number of state-action pairs however, so we can not say conclusively if 2000 episodes would be enough. $\endgroup$ Jun 16, 2020 at 15:20
-
$\begingroup$ We can decay the exploration rate (epsilon in most books) as the number of episodes increases though so after many thousands of episodes the probability of exploration is neglible. $\endgroup$ Jun 16, 2020 at 15:21
-
$\begingroup$ Oh okay, so everything is basically on saying we’re not sure if 2000 episodes would be enough especially if the state space is large, but we’ve gotten better Q values on state action pairs so we can make y 90% exploitation and 10%exploration $\endgroup$– ChukwudiJun 16, 2020 at 15:23
-
$\begingroup$ Exactly but now think if you continue until 20,000 episodes, your Q values are becoming more accurate and you have explored more of the state space and know that certain state-action pairs are terrible so exploring them even more is pointless, so you reduce exploration to say 9% and so on. If you have only been to a state a handful of times (especially if the resulting state is stochastic) you are unsure if it's a bad state - so you keep coming back. However, if you've been to a state 100 times and most of the time it sucked, you would be uninterested in going back. $\endgroup$ Jun 16, 2020 at 15:26
$\begingroup$
$\endgroup$
BlueTurtle's answer is good, but I'd like to add something.
Your question realistically has nothing to do with Q Learning, in fact, you can ask the same thing about just about any RL algorithm. In fact, even in multi-armed bandits, you can easily see why your proposed method is suboptimal (please don't interpret this as a criticism, because I think your question is a very natural one). My suggestion to you is to read up on multi-armed bandits since they're much simpler to analyze. I think even the Sutton and Barto book deals with your proposed method explicitly, and mathematically proves that other strategies are better.
