3
$\begingroup$

I have a network with nodes and links, each of them with a certain amount of resources (that can take discrete values) at the initial state. At random time steps, a service is generated, and, based on the agent's action, the network status changes, reducing some of those nodes and links resources.

The number of all possible states that the network can have is too large to calculate, especially since there is the random factor when generating the services.

Let's say that I set the state space large enough (for example, 5000), and I use Q-Learning for 1000 episodes. Afterwards, when I test the agent ($\max Q(s,a)$), what could happen if the agent faces a state that did not encounter during the training phase?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
2
$\begingroup$

Having too many states to actually visit is a common problem in RL. This is exactly why we often use function approximation. If you replace your q table with a good function approximator such as a neural network, it should be able to generelize well to states it has not yet encountered.

If you do not use a function approximator but stick with a table, the agent will have no idea what to do when it encounters a new state. For more information, see Reinforcement Learning by Sutton and Barto, chapter 9.

Improve this answer
$\endgroup$
0
1
$\begingroup$

I will try to explain this problem with the very tangible example of chess. In chess, the number of possible states is any configuration that you can make with the pieces on the board. So, the starting position is a state, and after you did one move you are in a different state. The total number of chess states is more than $10^{100}$. It is therefore very unlikely that a chess bot has seen all the states in training when playing a match.

So, how does the algorithm solve this? For the answer, we have to look at how an RL algorithm chooses which move is the best. This obviously depends on the implementation of the algorithm, but, generally, the calculation of 'how good' a move is, is done with the use of an approximation taking into account the 'potential future reward'. If you capture the queen, that would probably be good (not a chess expert here), even though you have not seen this exact state before. If you go further than this, a network might be able to approximate what happens many moves in the future. The specifics come down to implementation, etc., but this is the gist of it.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I'm not sure how this answers the question: "what could happen if the agent faces a state that did not encounter during the training phase?". In this answer, it seems that you're just describing what a value function is (apart from giving the example of chess, but that was not the question). So, can you clarify how this answers the question? $\endgroup$
    – nbro
    Dec 3, 2020 at 0:45
  • $\begingroup$ @nbro not an answer, but a valid commentary on the underlying problem in general, with a relatable example (chess) for which there has been robust validation of statistical techniques. $\endgroup$
    – DukeZhou
    Dec 3, 2020 at 1:46
  • $\begingroup$ @DukeZhou This answer contains some useful info, right, but it needs to be edited to more directly address the question. It seems that some info is missing. $\endgroup$
    – nbro
    Dec 3, 2020 at 10:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .