Answers.Body: <p>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 <strong>entire</strong> priority queue of <code>(website-outlink)</code> pairs + the <code>(new_website-outlink)</code> pairs. Your action is which pair you select.</p>
  <p>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 <code>state==observation</code> need <strong>not</strong> be (in general). So what is your observation? Your observation is a variable-sized batch of either:</p>
  <ol>
  <li><code>(website-outlink)</code> pairs <strong>or</strong></li>
  <li><code>next_website</code> (where each <code>next_website</code> is determined by its corresponding pair)</li>
  </ol>
  <p>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 &quot;which links to open before opening them&quot; or &quot;which links are meaningful (after opening them)&quot;.</p>
  <p>What your priority queue is essentially doing is just adding a neat trick that:</p>
  <ul>
  <li>Saves the computational complexity of keeping the state ordered (remember that your state is not a <code>website</code>, but the list/batch of <code>website-outlink</code>)</li>
  <li>Avoids needlessly recomputing the Q-values for each of your actions (remember that an action is not selecting an outlink from <code>new_website</code>, but selecting an outlink from all available choices in the queue)</li>
  </ul>
  <p>Note however that to actually have the second saving it is crucial to store the Q-values for each pair!!!</p>
  <p>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 <a href="https://en.wikipedia.org/wiki/Q-learning#Algorithm" rel="nofollow noreferrer">here</a>; your state <code>s_t</code> is a (quasi-ordered<sup>1</sup>) batch of pairs. <code>Q(s_t, a_t)</code> is just the output of running your DQN regression on <strong>just</strong> the best website/pair in this batch (you <strong>have</strong> 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 <strong>have to</strong> recompute the Q-value of every single website/pair in the next state. You CANNOT use the priority queue when training from the RB.</p>
  <p><sup>1<sub> You have the priority queue ordered for all websites you had in it whilst looking at the last website, but all the <code>new_website-outlink</code> 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 <code>new_new_website-outink</code> pairs). </sub></sup></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-03T22:31:33.670Z
Answers.Text: 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.
Answers.UserDisplayName: ddaedalus
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-03T22:33:33.040Z
Answers.Text: That is, in order to change state, update synchronously all pairs in frontier and select with e-greedy.
Answers.UserDisplayName: ddaedalus
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-05T07:42:01.443Z
Answers.Text: 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
Answers.UserDisplayName: Federico Malerba
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-03T08:38:21.760Z
Answers.LastActivityDate: 2021-01-03T08:38:21.760Z
Answers.UserDisplayName: Federico Malerba
Body: <p>In my problem, the agent does not follow the successive order of states, but selects with <span class="math-container">$\epsilon$</span>-greedy the best pair (state, action) from a priority queue. More specifically, when my agent goes to a state <span class="math-container">$s$</span> and opens its available actions <span class="math-container">$\{ a_i \}$</span>, then it estimates each <span class="math-container">$(s,a)$</span> pair (regression with DQN) and stores it into the queue. In order for my agent to change to state <span class="math-container">$s'$</span>, it picks the best pair from the queue instead of following one of the available actions <span class="math-container">$\{ a_i \}$</span> of <span class="math-container">$s$</span>. I note that a state has a partially-different action set from the others.</p>
  <p>However, in this way, how can I model my MDP if my agent does not follow the successive order of states?</p>
  <p>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.</p>
  <ul>
  <li>State: the webpage,</li>
  <li>Actions: the outlink URLs of the state webpage,</li>
  <li>Reward: from external source I know if the webpage content is relevant.</li>
  </ul>
  <p>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.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T17:18:44.873Z
Comments.Text: 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?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T17:25:49.237Z
Comments.Text: 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'.
Comments.UserDisplayName: ddaedalus
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T17:28:32.237Z
Comments.Text: 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)?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T17:30:35.953Z
Comments.Text: 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?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T17:30:41.267Z
Comments.Text: Yes, I guess. But the current point-state can only estimate its actions and not all actions seen in trajectory
Comments.UserDisplayName: ddaedalus
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T17:32:58.590Z
Comments.Text: How can I insert in my MDP formula the priority queue for the previous (state,action) pairs that tells which is the next state ?
Comments.UserDisplayName: ddaedalus
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T17:33:45.067Z
Comments.Text: That's not a restriction that the environment can impose. Clearly if it has no data, any value estimate may be incorrect, but evaluation (or not) of a state or state/action pair is not an action, it is integral to the agent and cannot be restricted. Unless you have some interaction allowed with the environment which fetches some additional values . . . if so, may be better not to call that "estimates" or "evaluation"?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T17:36:35.223Z
Comments.Text: I think you are going to need to explain more about your environment in your question and how/why you have modelled it this way. It is not clear why you have done this, and you are likely to be stretching the meaning of RL terminology to cover what you are doing - it might be fine, but it is hard to understand what you are attempting to do
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T17:44:04.733Z
Comments.Text: Is it clarified more now ?
Comments.UserDisplayName: ddaedalus
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T17:53:30.317Z
Comments.Text: Yes it is clearer. You could clarify one more thing - is the backtracking/priorising of earlier links something you want the agent to do only during training (to prevent blocks during training), or is it also the behaviour that you want in the optimal agent?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T17:55:14.573Z
Comments.Text: I want the non-succesive move in the optimal agent too
Comments.UserDisplayName: ddaedalus
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T17:58:42.400Z
Comments.Text: The idea, except for finding relevant pages in a direct way, is to identify hubs ; new webpages (states) that are possibly irrelevant but extract relevant urls (actions).
Comments.UserDisplayName: ddaedalus
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-30T19:10:40.827Z
Comments.Text: Maybe I can assume that each state(webpage) has an action(URL) for all pages(states).So there is a transition probability for all states.Assuming that we are in s, the DQNAgent would output a Q-value for each action a and with this value the pair (s,a) would be inserted in queue.New_state comes from the action that the best pair (state,action) in queue has.So currentstate retains the action values of the past states for all actions seen and only estimates its own actions.In ER store the record (state,action,reward,new_state) with state being the webpage truely extracted this action.Is it fair?
Comments.UserDisplayName: ddaedalus
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-31T15:53:41.137Z
Comments.Text: I've changed the title of this post. Make sure that the title is your actual question.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><dqn><markov-decision-process>
Title: How can I model a problem as an MDP if the agent does not follow the successive order of states?
UserDisplayName: ddaedalus
ThreadText: # How can I model a problem as an MDP if the agent does not follow the successive order of states?
  
  (Asked by: username_0 on 2020-12-30)
  
  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.
  
  **Tags:** reinforcement-learning, dqn, markov-decision-process
  
  > **Comments:**
  > **username_1**: 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?  
  > **username_0**: 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'.  
  > **username_1**: 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)?  
  > **username_1**: 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?  
  > **username_0**: Yes, I guess. But the current point-state can only estimate its actions and not all actions seen in trajectory  
  > **username_0**: How can I insert in my MDP formula the priority queue for the previous (state,action) pairs that tells which is the next state ?  
  > **username_1**: That's not a restriction that the environment can impose. Clearly if it has no data, any value estimate may be incorrect, but evaluation (or not) of a state or state/action pair is not an action, it is integral to the agent and cannot be restricted. Unless you have some interaction allowed with the environment which fetches some additional values . . . if so, may be better not to call that "estimates" or "evaluation"?  
  > **username_1**: I think you are going to need to explain more about your environment in your question and how/why you have modelled it this way. It is not clear why you have done this, and you are likely to be stretching the meaning of RL terminology to cover what you are doing - it might be fine, but it is hard to understand what you are attempting to do  
  > **username_0**: Is it clarified more now ?  
  > **username_1**: Yes it is clearer. You could clarify one more thing - is the backtracking/priorising of earlier links something you want the agent to do only during training (to prevent blocks during training), or is it also the behaviour that you want in the optimal agent?  
  > **username_0**: I want the non-succesive move in the optimal agent too  
  > **username_0**: The idea, except for finding relevant pages in a direct way, is to identify hubs ; new webpages (states) that are possibly irrelevant but extract relevant urls (actions).  
  > **username_0**: Maybe I can assume that each state(webpage) has an action(URL) for all pages(states).So there is a transition probability for all states.Assuming that we are in s, the DQNAgent would output a Q-value for each action a and with this value the pair (s,a) would be inserted in queue.New_state comes from the action that the best pair (state,action) in queue has.So currentstate retains the action values of the past states for all actions seen and only estimates its own actions.In ER store the record (state,action,reward,new_state) with state being the webpage truely extracted this action.Is it fair?  
  > **username_2**: I've changed the title of this post. Make sure that the title is your actual question.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2021-01-03. Score: 1
  
  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](https://en.wikipedia.org/wiki/Q-learning#Algorithm); 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).
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_0**: That is, in order to change state, update synchronously all pairs in frontier and select with e-greedy.  
  > **username_3**: 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  
  
  ---
  
  