5
$\begingroup$

In Q-learning, all resources I've found seem to say that the algorithm to update the Q-table should start at some initial state, and pick actions (which are sometimes random) to explore the state space.

However, wouldn't it be better/faster/more thorough to simply iterate through all possible states? This would ensure that the entire table is updated, instead of just the states we happen to visit. Something like this (for each epoch):

for state in range(NUM_STATES):
  for action in range(NUM_ACTIONS):
    next_state, reward = env.step(state, action)
    update_q_table(state, action, next_state, reward)

Is this a viable option? The only drawback I can think of is that it wouldn't be efficient for huge state spaces.

$\endgroup$
5
$\begingroup$

If your algorithm is executed multiple (or enough) times using an outer loop, it would converge to similar results as Q-learning would with $\gamma = 0$ (as you don't look what is the expected future reward).

In this case, the difference is that you would pass as much time to explore each possible couple of (state, action) while Q-learning would pass more time on the pair which seem more promising and, as you've said this wouldn't be efficient for a problem with a huge number of pair (state, action).

If the algorithm is executed only once, then, even for a problem with a few pairs (state, action), you need to assume that an action effected on a state will always bear the same result for your method to work.

In most cases, it isn't true either because there is some sort of randomness in the reward system or in the action (your agent can fail to make an action) or because the state of your agent is limited to its knowledge and so doesn't represent perfectly the world (and so the consequence of its action can vary just like if the reward had some randomness).

Finally, your algorithm doesn't look at the expected future reward, so it would be equivalent to having $\gamma = 0$. This could be fixed by adding a new loop updating the table after your current loops if you execute your algorithm only one time or by adding the expected future reward directly to your Q-table if there is an outer loop.

So, in conclusion, without the outer loop, your idea would work for a system with few pairs of (state, action), where your agent has a perfect and complete knowledge of its world, the reward doesn't vary, and where an agent can't fail to accomplish an action.

While these kinds of systems indeed exist, I don't think that it's an environment where one should use Q-learning (or another form of reinforcement learning), except if it's for educational purposes.

With an outer loop, your idea would work if you are willing to pass more time training to have a more precise Q-table on the least promising pair of (state, action).

$\endgroup$
4
  • $\begingroup$ I indeed assumed that there is no outer loop and that the algo was limited to what was shown. I will edit the answer to make it clear. Assuming that there is no outer loop and a deterministic environment the algo is indeed equivalent to having γ = 0, I will also make it clear in my answer but it's a problem that could be easily fixed so I don't think that it's the core of the problem. $\endgroup$ – kirua Feb 1 at 10:30
  • $\begingroup$ By "outer loop" I assume you mean training epochs? I added that to my question - indeed a single pass would just fill in initial values for the table, but it would require further passes for those values to converge. $\endgroup$ – Kricket Feb 1 at 10:45
  • $\begingroup$ An "outer loop" would repeat the algo. It could be a fixed number of time which is equivalent to trainings epoch or until convergence (ie, the Q-table isn't updated anymore) $\endgroup$ – kirua Feb 1 at 10:47
  • $\begingroup$ Indeed, in my case the state space is continuous, but I'm using a discretized representation - and so since there is a range of possible "real" states represented by a given discrete state, the result of a given action is not necessarily deterministic. $\endgroup$ – Kricket Feb 1 at 10:48
2
$\begingroup$

In short, yes, provided that you have a small number of states.

In pretty much any real system, the number of states is much higher than you could ever hope to explore exhaustively in any reasonable time. This is why you need to set some sort of exploration/exploitation policy to make sure that you mostly visit promising states while also checking states that might look initially poor but may lead to better states as you explore further. As a few minutes thought will convince you, determining the exact nature of that exploration/exploitation trade-off is probably the most important aspect of effective Q-Learning (and pretty much any other search algorithm for that matter).

$\endgroup$
-2
$\begingroup$

The issue is trading off reward vs learning, Q-learning attempts to learn and do things which produce reward(basically, operate suboptimally).

I'm not sure if Q-Learning is actually any different performance wise, short-term Q-Learning will produce more reward(probably) but will also miss states.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.