Answers.Body: <p>You have two options, either interpolate or restrict the actions only to values that produce states which are in your state vector. </p>
  
  <p>The simplest interpolation scheme is a linear interpolation, which works as follows (assuming <code>DS</code> contains a set of grid points in increasing order). For a state <span class="math-container">$s'$</span> you can locate its closest neighbours from the array <code>DS</code> and the value in state <span class="math-container">$s'$</span> will, then, be a weighted average of the values in those neighbouring states. Formally, <span class="math-container">$$Q(s') = \frac{s_{i+1} - s'}{s_{i+1}-s_i}Q(s_i) + \frac{s'-s_i}{s_{i+1}-s_i}Q(s_{i+1}),$$</span> for <span class="math-container">$s_i &lt; s'&lt; s_{i+1}$</span>, where <span class="math-container">$s_i$</span> and <span class="math-container">$s_{i+1}$</span> are the neighbours, <span class="math-container">$s_i$</span> is the <span class="math-container">$i$</span>-th element of <code>DS</code>(i.e. <code>si = DS[i] = Q-table[i,1]</code>), and <span class="math-container">$Q(s_i)$</span> is related to the Q-table as <code>Qsi = Q-table[i,2]</code> (asuming array indexing starts from 1). </p>
  
  <p>Restricting the actions would work as follows. For simplicity, assume that the agent chooses the next state directly, i.e. <span class="math-container">$s'=a$</span>. Then, if you have an array of actions <code>A = [a1, a2, ... , aM]</code>, <span class="math-container">$M \le N$</span> then each <span class="math-container">$a_i$</span> needs to be present in the state array <code>DS</code> (i.e. <code>A</code> is a subset of <code>DS</code>, formally <span class="math-container">$A \subseteq S$</span>). This may not be desirable but it is an option. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-25T20:18:23.990Z
Answers.Text: Hi and welcome to AI SE! Thanks for contributing! Note that you can use MathJax on this site, so you use write beautiful equations :) You just need to wrap the equations with the symbol `$` on both sides. I suggest you do it to improve the readability of your answer!
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-25T16:13:42.083Z
Answers.LastActivityDate: 2020-05-27T07:43:05.557Z
Answers.LastEditDate: 2020-05-27T07:43:05.557Z
Answers.UserDisplayName: PetrH
Body: <p>I am using Q-learning to solve an engineering problem. The objective is to generate a Q-table associating state to Q-values. </p>
  
  <p>I created a State vector <code>DS = [s1, s2, ..., sN]</code> containing all "desired" states. So the Q-table has the form of <code>Q-table =[DS, Q-values]</code>. </p>
  
  <p>On the other hand, my agent follows a trajectory. Playing action <code>a</code> at state <code>s</code> (which is a point of the trajectory) leads the agent to another state <code>s'</code> (another point of the trajectory). However, I don't have the <code>s'</code> state in the initially desired states vector <code>DS</code>. </p>
  
  <p>One solution is to add new states to the <code>DS</code> vector while the Q-learning algorithm is running, but I do not want to add new states. </p>
  
  <p>Any other ideas on how to handle this problem? </p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-24T22:07:22.147Z
Comments.Text: Why don't you want to add the new states? You will need to know their values later in order to make decisions in them, should the agent encounter them again, plus to update the preceding state's action values more accurately.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-25T03:55:41.887Z
Comments.Text: Actually, I want to restrict the number of states the system can be in. But following the 'trajectory', the agent can be in some non-initially defined states.
Comments.UserDisplayName: moby91
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-25T04:10:47.077Z
Comments.Text: Is there any specific reason you want to restrict the number of states? What if the optimal path is through the states you are looking to restrict?
Comments.UserDisplayName: pecey
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-25T19:34:55.320Z
Comments.Text: I think you need to clarify further. In general it does not make sense to simultaneously allow transition to a state, yet refuse to track its action values. If your state restriction is absolute, and possible to impose on the agent (like the rules of a game), then typically you do not allow the transition (making tracking values a non-issue). If your state restriction cannot be enforced, but you want to avoid the states as part of the goals of the agent, then you will need to track them (plus maybe have some consequences such as negative rewards). Could you please [edit] in more details?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-26T10:09:03.593Z
Comments.Text: @pecey My best guess is that the OP is dealing with a continuous-space problem and they approximate the space by a finite set of grid points. In that case, adding one more state will not be a solution as that will only produce another state which is not on the grid.
Comments.UserDisplayName: PetrH
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-26T10:23:51.900Z
Comments.Text: @NeilSlater The OP does not want to refuse to track the state's value, they just do not know how to do it without adding the state in their set of states. Function approximation solves this problem (perhaps mitigates rather than solves).
Comments.UserDisplayName: PetrH
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-26T10:52:38.400Z
Comments.Text: @PetrH: That's a possibility, but IMO is not clear from the question. I upvoted your answer on the grounds that it addresses that interpretation. However, the OP's use of the terms "non-existing states" and "desired states" in the question title implies something different is going on. Those "desired" states *might* be reference points in a continuous space, but nothing else in the question makes that an obvious interpretation
Comments.UserDisplayName: Neil Slater
Tags: <reinforcement-learning><q-learning><dqn><deep-rl>
Title: Handle non-existing states in q-learning
UserDisplayName: moby91
ThreadText: # Handle non-existing states in q-learning
  
  (Asked by: username_0 on 2020-05-24)
  
  I am using Q-learning to solve an engineering problem. The objective is to generate a Q-table associating state to Q-values.
  
  I created a State vector `DS = [s1, s2, ..., sN]` containing all "desired" states. So the Q-table has the form of `Q-table =[DS, Q-values]`.
  
  On the other hand, my agent follows a trajectory. Playing action `a` at state `s` (which is a point of the trajectory) leads the agent to another state `s'` (another point of the trajectory). However, I don't have the `s'` state in the initially desired states vector `DS`.
  
  One solution is to add new states to the `DS` vector while the Q-learning algorithm is running, but I do not want to add new states.
  
  Any other ideas on how to handle this problem?
  
  **Tags:** reinforcement-learning, q-learning, dqn, deep-rl
  > **Comments:**
  > **username_1**: Why don't you want to add the new states? You will need to know their values later in order to make decisions in them, should the agent encounter them again, plus to update the preceding state's action values more accurately.  
  > **username_0**: Actually, I want to restrict the number of states the system can be in. But following the 'trajectory', the agent can be in some non-initially defined states.  
  > **username_2**: Is there any specific reason you want to restrict the number of states? What if the optimal path is through the states you are looking to restrict?  
  > **username_1**: I think you need to clarify further. In general it does not make sense to simultaneously allow transition to a state, yet refuse to track its action values. If your state restriction is absolute, and possible to impose on the agent (like the rules of a game), then typically you do not allow the transition (making tracking values a non-issue). If your state restriction cannot be enforced, but you want to avoid the states as part of the goals of the agent, then you will need to track them (plus maybe have some consequences such as negative rewards). Could you please [edit] in more details?  
  > **username_3**: @pecey My best guess is that the OP is dealing with a continuous-space problem and they approximate the space by a finite set of grid points. In that case, adding one more state will not be a solution as that will only produce another state which is not on the grid.  
  > **username_3**: @NeilSlater The OP does not want to refuse to track the state's value, they just do not know how to do it without adding the state in their set of states. Function approximation solves this problem (perhaps mitigates rather than solves).  
  > **username_1**: @PetrH: That's a possibility, but IMO is not clear from the question. I upvoted your answer on the grounds that it addresses that interpretation. However, the OP's use of the terms "non-existing states" and "desired states" in the question title implies something different is going on. Those "desired" states *might* be reference points in a continuous space, but nothing else in the question makes that an obvious interpretation  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2020-05-25. Score: 2
  
  You have two options, either interpolate or restrict the actions only to values that produce states which are in your state vector.
  
  The simplest interpolation scheme is a linear interpolation, which works as follows (assuming `DS` contains a set of grid points in increasing order). For a state $s'$ you can locate its closest neighbours from the array `DS` and the value in state $s'$ will, then, be a weighted average of the values in those neighbouring states. Formally, $$Q(s') = \frac{s\_{i+1} - s'}{s\_{i+1}-s\_i}Q(s\_i) + \frac{s'-s\_i}{s\_{i+1}-s\_i}Q(s\_{i+1}),$$ for $s\_i < s'< s\_{i+1}$, where $s\_i$ and $s\_{i+1}$ are the neighbours, $s\_i$ is the $i$-th element of `DS`(i.e. `si = DS[i] = Q-table[i,1]`), and $Q(s\_i)$ is related to the Q-table as `Qsi = Q-table[i,2]` (asuming array indexing starts from 1).
  
  Restricting the actions would work as follows. For simplicity, assume that the agent chooses the next state directly, i.e. $s'=a$. Then, if you have an array of actions `A = [a1, a2, ... , aM]`, $M \le N$ then each $a\_i$ needs to be present in the state array `DS` (i.e. `A` is a subset of `DS`, formally $A \subseteq S$). This may not be desirable but it is an option.
  
  > **Comments:**
  > **username_4**: Hi and welcome to AI SE! Thanks for contributing! Note that you can use MathJax on this site, so you use write beautiful equations :) You just need to wrap the equations with the symbol `$` on both sides. I suggest you do it to improve the readability of your answer!  
  
  ---
  
  