I have already asked 2-3 general questions w.r.t Q learning and now I am asking a scenario specific one. I will try to be concise and understandable. I really really need help.

Scenario: I have a network with few nodes and links. On each link, there are some slots (#1 to #800). I generate traffic requests (come one by one) that want to go from one node to another and need certain slots to do so. So, my task is to allot the slots to each upcoming request and finally achieve a low rejection probability i.e. able to allot slots to as many requests as possible. The allotted slots are also freed up depending on when the arrived requests leave the system. I use the Poisson process to do, but this is not important here.

What I thought: There have been certain simple benchmarks to do this but I wanted to use Q learning so that in the long run the agent (a centralized controller) takes better decisions as to which slots to assign on the particular link i.e. which slots position (#1 to #800).

What I did: I decided to take the state space as the links (say 10 links in my case) and the action space as the #1 to #800 slots. I use binary notation 1 to say slot is occupied or 0 that is free.

Problem encountered: But it is long later I realized that my state space is infinitely big. For E.g. For request 1, I give two slots on Link1 & state is 1 1 0 0 0 .... up to 800 zeros. Another request comes (say 3 slots) and say Link1 state is now 1 1 1 1 1 0 0 0...up to 800 zeros. This is when I realized that the state space is unimaginably large as departures can also occur leading to freeing up and some 1s becoming 0s and so on.

What I am asking for: So, does anyone have any ideas on how can I still use Q learning in this case. The point is that someone already used deep Q on this. I was thinking I am approaching it in a different and simplified way of just using link state as state space that would enable me to have a small Q table. But it is later I realized that each link state will vary every time and lead to large state space thus putting me back to square one after investing a lot of time on this. So, please give any suggestions as I don't want to leave it altogether.

  • 1
    $\begingroup$ I am not clear on this: The requests require "certain slots" - so the slot numbers needed are somehow specified in the request? However, you also say that action description is the slot number to assign, which must therefore mean the agent is free in at least some extent to make a choice other than accept/reject a request? How much freedom the agent has is important in understanding the true size of the state space and action space here. $\endgroup$ Nov 20, 2021 at 7:49
  • 1
    $\begingroup$ For instance, if all slots are equivalent, and requests only specify the number of slots required, your state space would be size 800 and action space size 2. I would not expect that to be the case, since you would probably have figured that out. However, it is not clear from the question why that is the case, what specifically prevents you from having necessary information about the state of the system for decisions by the agent in a simplified form. Knowing this is necessary if you want someone else to verify your assessment of the state space size. $\endgroup$ Nov 20, 2021 at 7:52
  • $\begingroup$ @NeilSlater Thanks for the comments. If I understood your question correctly, I would say that the scenario is that the request asks for a certain no. of slots (say 3), I have find &allot 3 slots on the respective links it will travel. The #800 slots are increasing in a frequency value. It is like I choose the frequency(slot) to assign it. But I should give 3 continuous slots for e.g. slot no. 35 36 37. Since this alloting slots has effect on certain paramters (which I consider in reward) I decided to make the first slot selection as 'actions'. $\endgroup$ Nov 20, 2021 at 22:56
  • $\begingroup$ @NeilSlater Nothing prevents me from knowing the information of the state. At any time I can access the link_slots variable to see the occupancy in each link. Since I have 10 links I thought ok, maybe my states are my links (#1 to #10) and actions the corresponding frequency slots (#1 to #800) . But later did I realize (as int he question e.g.) that the each link's state i.e. the combination of 1's and 0's would be different everytime and I cannot use the updated Q value (say) of slot #35 at a later time to give the same slot to another request (assuming now that slot is free). $\endgroup$ Nov 20, 2021 at 22:59
  • $\begingroup$ @NeilSlater I thought so because the state of that link when I updated the Q value for 'its' #35 slot action and the link state 'now' are different, when I am trying to decide to give the same #35 slot for my current request on that same link jsut because I see the Q value is good for #35 action. But this is a new combiantion of 1's and 0's & so it is a new unseen state for the same link. The e.g. in the question illustrates this. I don't know if my conclusions regarding Q learning in this case are right though... $\endgroup$ Nov 20, 2021 at 23:02


You must log in to answer this question.

Browse other questions tagged .