1
$\begingroup$

In my problem, the agent does not follow the successive order of states, but selects with $\epsilon$-greedy the best pair (state, action) from a priority queue. More specifically, when my agent goes to a state $s$ and opens its available actions $\{ a_i \}$, then it estimates each $(s,a)$ pair (regression with DQN) and stores it into the queue. In order for my agent to change to state $s'$, it picks the best pair from the queue instead of following one of the available actions $\{ a_i \}$ of $s$. I note that a state has a partially-different action set from the others.

However, in this way, how can I model my MDP if my agent does not follow the successive order of states?

More specifically, I have a focused crawler that has an input of a few seeds URLs. I want to output as many as possible relevant URLs with the seeds. I model the RL framework as follows.

  • State: the webpage,
  • Actions: the outlink URLs of the state webpage,
  • Reward: from external source I know if the webpage content is relevant.

The problem is that, while crawling, if the agent keeps going forward by following the successive state transition, it can fall into crawling traps or local optima. That is the reason why a priority queue is used importantly in crawling. The crawling agent does not follow anymore the successive order of state transitions. Each state-action pair is added to the priority queue with its estimated action value. For each time, it selects the most promising state-action pair among all pairs in the queue. I note that each URL action can be estimated taking into account the state-webpage where it was extracted.

Improve this question
$\endgroup$
14
  • $\begingroup$ Could you clarify - is this non-sequential ordering of states only part of the training process that you have implemented, or is it integral to the environment? Is there any meaningful state transition rule? $\endgroup$ – Neil Slater Dec 30 '20 at 17:18
  • $\begingroup$ The environment says that if you are in a state s then estimate all its available actions {a} and then choose the best action from all past states, including current, and move to s'. $\endgroup$ – ddaedalus Dec 30 '20 at 17:25
  • $\begingroup$ That doesn't appear to be a description of an environment, but some combination of agent and environment. Ignoring the evaluation step (which is not part of the environment definition), are you saying that the state of the environment is the current state plus all historical states, and the agent can choose to act within the context of any state seen so far (i.e. it can effectively extend the trajectory from any point in history)? $\endgroup$ – Neil Slater Dec 30 '20 at 17:28
  • $\begingroup$ Or another way to put this is the agent's action effectively both choosing which state to use (out of states it has seen) plus a choice that it can make within that state? $\endgroup$ – Neil Slater Dec 30 '20 at 17:30
  • $\begingroup$ Yes, I guess. But the current point-state can only estimate its actions and not all actions seen in trajectory $\endgroup$ – ddaedalus Dec 30 '20 at 17:30
1
$\begingroup$

Your problem fundamentally is that you are confusing what the state and actions are in this setting. Webpages are not your states; your state is the entire priority queue of (website-outlink) pairs + the (new_website-outlink) pairs. Your action is which pair you select.

Now this is a variable sized state-space and variable sized action-space problem setting at the same time. To deal with this lets start by noting that state==observation need not be (in general). So what is your observation? Your observation is a variable-sized batch of either:

  1. (website-outlink) pairs or
  2. next_website (where each next_website is determined by its corresponding pair)

Both of these observations could work just fine, choosing between one or the other is just a matter of whether you want your agent to learn "which links to open before opening them" or "which links are meaningful (after opening them)".

What your priority queue is essentially doing is just adding a neat trick that:

  • Saves the computational complexity of keeping the state ordered (remember that your state is not a website, but the list/batch of website-outlink)
  • Avoids needlessly recomputing the Q-values for each of your actions (remember that an action is not selecting an outlink from new_website, but selecting an outlink from all available choices in the queue)

Note however that to actually have the second saving it is crucial to store the Q-values for each pair!!!

Last important thing to note is that in a scenario where you use a Replay Buffer (which I guess is likely given that you chose a DQN), you can't use the priority queue whilst learning from the RB. To see why (and to see in detail how your learning process actually looks like), start by remembering that your Q-value updates are given by the formula here; your state s_t is a (quasi-ordered1) batch of pairs. Q(s_t, a_t) is just the output of running your DQN regression on just the best website/pair in this batch (you have to add an index to denote the best choice when adding transitions to the RB, in order to be consistent about which action was taken from this state). To compute the estimate of the optimal future value however you will have to recompute the Q-value of every single website/pair in the next state. You CANNOT use the priority queue when training from the RB.

1 You have the priority queue ordered for all websites you had in it whilst looking at the last website, but all the new_website-outlink pairs you are now adding are not ordered yet. You still have to run the agent on them and then you can order them with the rest of the priority queue to generate the next state (which still will not be ordered because you will have new_new_website-outink pairs).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the answer. With my modeling of MDP, what is wrong? State: webpage that has possible actions for all other states. Action: single url. A state has the actions for all URLs directly extracted by the current state webpage plus the actions seen in past states. In queue, store pairs (s,a) with a directly extracted from s. And in ER store records <(s,a), r, s'> with a directly extracted from s and not necessary from the last state. Update DQN with the max operator using only actions directly extracted from s' and not all actions seen. After this, update all pairs in queue. etc. $\endgroup$ – ddaedalus Jan 3 at 22:31
  • $\begingroup$ That is, in order to change state, update synchronously all pairs in frontier and select with e-greedy. $\endgroup$ – ddaedalus Jan 3 at 22:33
  • $\begingroup$ Well the issue is that you can't just select whatever you want as a state. MDP requires that the transitions be state-action-nextstate. If you define a state in a way such that this isn't true (because in your description nextstate could be relative to a previously seen website) then you have defined your state wrong. This is why nothing will work or make sense. You have to expand your state. This is what my proposed solution does by inlcuding the entire queue as the state while still implementing some computational shortcuts at run time $\endgroup$ – Federico Malerba Jan 5 at 7:42

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.