0
$\begingroup$

I read the working of Q-learning through a grid-based taxi routing wherein a taxi has to pick and drop off a passenger from source to destination. Likewise, I have a routing problem and hence, I tried adapting the code from the article for my scenario. Visiting this page is not required, just gave the link for reference. https://www.learndatasci.com/tutorials/reinforcement-q-learning-scratch-python-openai-gym/

My Scenario: As an analogy to my network routing, say my source & destination are node A and node E. Say only two routes are possible: A-B-E and A-B-C-E. I want to select the next node at each 'action' stage that finally together forms a route. Hence, I take my 'state' and 'action' both as the set of all nodes.

Problem: BUT my reward is a value I assign that depends on the parameters of the links connecting the nodes. i.e.if I compute some network metric as x for the link A-B then I give this x as the reward since I want to minimize the x in my network. And obviously, this x would differ over time since my network links' status changes. It is not something I can pre-define for a given state-action as in the article example like obstacle means negative reward, destination means positive reward,etc.

So what should I do in this case? Is my definition of 'state' or 'action' wrong? Or do I need a deep Q-network? Is it for such kinds of cases? Please suggest.

$\endgroup$

1 Answer 1

1
$\begingroup$

Is my definition of 'state' or 'action' wrong?

I hesitate to say 'wrong', but that's not how state and action are defined in RL, and that mismatch might make the algorithms hard to understand.

In RL theory, the set of all nodes and the links between them is called the environment, the agent's current location is the state, and taking a route from one node to the next is the action. The reward is just as you said, except that usually the agent is trying to maximize the reward.

Once your terms are aligned, regular Q learning (which keeps a simple table of Q values instead of approximating the Q values with something like a neural network) should actually work better than deep Q learning on such a small problem, because training a neural net can be challenging.

Which brings us to the changing rewards. When the rewards change, the agent will need to find the new optimal path. To do that it will need to explore more than it would for a problem with fixed rewards that can settle into an optimal solution. For example, if you were using epsilon greedy exploration, epsilon would need to remain large, or be reset to a large value when the rewards change.

Of course, the agent will perform poorly until it adapts to the new rewards, but you might be able to recalculate the optimal route when the parameters change by running the simulation for some time before making any real decisions.

Hope that helps

$\endgroup$
8
  • $\begingroup$ Thanks for the detailed answer. I understand your view about dealing with changing rewards part. Actually this was precisely the reason why I was thinking that the tabular approach might not work. The below comment was my thought process. Please read it and tell me if there is a flaw. $\endgroup$ Jun 10, 2022 at 2:16
  • $\begingroup$ My thought process, "ok, if I take state as the current position (which is a node) it would be finite in number. But as much as I may define the state as the current position i.e. a node number, my reward still depends on a link metric that can take any value which is similar to choosing a link as a state since choosing which next link or which next node are synonymous. And so maybe I need a DQN as the link metric will take different values". I think I confuse between choosing a link vs node number i.e. current position as my state... $\endgroup$ Jun 10, 2022 at 2:21
  • 1
    $\begingroup$ "choosing which next link or which next node are synonymous". Yep, you could think of that either way. "And so maybe I need a DQN as the link metric will take different values" I don't follow this part. A Q value in the table of Q values in regular Q learning can also change, and will change faster and be more accurate than an estimated Q value from the neural network in DQN. $\endgroup$
    – Lee Reeves
    Jun 10, 2022 at 2:37
  • 1
    $\begingroup$ Perhaps this will help: Q learning calculates a function Q(s,a) whose values are precisely updated according to the Bellman equation. DQN tries to estimate Q(s,a), but those estimates aren't as good as knowing the true value. $\endgroup$
    – Lee Reeves
    Jun 10, 2022 at 2:40
  • 1
    $\begingroup$ It's ok if the metrics/rewards and the Q-values are continuous, only the number of actions (options) needs to be finite. For example, if there were two links leading out of a node, the Q value table would only need two entries for that node, one per link, even if the metric/reward for each link were unconstrained. $\endgroup$
    – Lee Reeves
    Jun 10, 2022 at 2:45

You must log in to answer this question.

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