1
$\begingroup$

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?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Neil Slater May 24 '20 at 22:07
  • $\begingroup$ 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. $\endgroup$ – moby91 May 25 '20 at 3:55
  • 1
    $\begingroup$ 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? $\endgroup$ – pecey May 25 '20 at 4:10
  • $\begingroup$ 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? $\endgroup$ – Neil Slater May 25 '20 at 19:34
  • 1
    $\begingroup$ @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 $\endgroup$ – Neil Slater May 26 '20 at 10:52
2
$\begingroup$

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.

Improve this answer
$\endgroup$
  • 2
    $\begingroup$ 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! $\endgroup$ – nbro♦ May 25 '20 at 20:18

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.