2
$\begingroup$

In Q-learning, is it mandatory to know all possible states that can the agent may end up in?

I have a network with 4 source nodes, 3 sink nodes, and 4 main links. The initial state is the status network where the sink nodes have its resources at its maximum. In a random manner, I generate service requests from the source nodes to the sink nodes. These service requests are generated at random timesteps, which means that, from state to state, the network status may stay the same.

When a service request is launched, the resources from the sink nodes change, and the network status changes.

The aim of the agent is to balance the network by associating each service request to a sink node along with the path.

I know that in MDP you are supposed to have a finite set of states, my question is: if that finite set of states is supposed to be all possible states that can happen, or is just a number that you consider enough to optimize the Q-table?

$\endgroup$
1
$\begingroup$

When you start off learning about Q-learning, you start with a simple example that has a few states. For each of the states, you try to estimate what the 'value' is of that state. Because there are so few states, it is possible to store these values in a table (it is also useful for the intuitiveness of the explanation).

However, if you start trying to solve more 'real-life' problems, the number of states can be insanely huge. The essence however will stay the same. You are trying to estimate what you want to do next, based on an estimation of how good each state is that you can end up in. However, now the values are 'most of the times' not stored in a table anymore, as the approach will often come down to using an ANN to estimate the value function.

Answer to your question: You are going to run into a lot of problems when training some model with Q-learning if your table is not able to store the values of possible states that it can come across. In practice, most implementations do not use a Q-table and just use an ANN, which alleviates the problem of having to 'define' how many states your problem consists of.

$\endgroup$
1
  • $\begingroup$ If you feel like this answer answered your questions correctly or sufficiently, make sure to approve the answer by clicking the checkmark :) $\endgroup$ – Robin van Hoorn Dec 9 '20 at 8:29

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.