Answers.Body: <p>For general advice about state representation, you could check my answer to <a href="https://ai.stackexchange.com/questions/7763/how-to-define-states-in-reinforcement-learning/7771#7771">How to define states in reinforcement learning?</a> - this does not cover your specific issue, but may help with other details such as whether to one-hot-encode and/or scale your discrete features. Also you will want to assess whether any state vector you construct actually contains <em>enough</em> data for reinforcement learning to work.</p>
  
  <p>Assuming that is all good, then your approach here:</p>
  
  <blockquote>
    <p>Can I simply vectorize such state by concatenating the different features of each element obtaining <span class="math-container">$[f_{0e_0}, f_{1e_0}, f_{0e_1}, f_{1e_1}, f_{0e_2}, f_{1e_2}]$</span></p>
  </blockquote>
  
  <p>should work with a generic feed-forward neural network with two or more layers. As this is simple to construct, then it is a reasonable place to start just considering development time. If nothing else it can be a benchmark against other representations and model architectures that you may want to try.</p>
  
  <blockquote>
    <p>should I use a convolutional architecture of some sort?</p>
  </blockquote>
  
  <p>That will depend on any structure inherent in your environment. The <em>interesting</em> thing about your description of the environment is the repetition of <em>meaning</em> in the values. Each entity <span class="math-container">$e_i$</span> appears multiple times, and the units of feature <span class="math-container">$f_{0e_0}$</span> will be the same as <span class="math-container">$f_{0e_1}$</span>. </p>
  
  <p>An unfortunate consequence of using a flattened vector is that the information about these repeated entities and their units is lost to the system. Any important details due to the entities being essentially the same of this must be "rediscovered" by the approximator training with many examples. Although neural networks can generalise function results, this does not apply to generalising across different parts of the input unless you choose an architecture designed to help with that.</p>
  
  <p>Typically you would use a RNN architecture (such as LSTM) if key information is in the <em>sequence order</em> of entities, or a CNN architecture if key information is in local patterns between neighbouring entities. By "key information" I mean whether useful relationship to a value function or optimal policy depends on those factors. This might be difficult to assess for some environments with mixed data types and complex meanings for the entity ids - so you may have to experiment with multiple architectures to figure out what factor is more important. However, it is also possible you have some insight based on known good policies, so can head more directly to a promising feature representation and architecture.</p>
  
  <p>Learning may benefit if instead of ordering your entities arbitrarily by identity in the vector, that you sort them according to some factor that is relevant to the goals of your agent. I have used this is in a colour matching environment where an agent had to hit a target with a "current" colour selection whilst avoiding incorrect colours - sorting target entities by whether they matched colour and then by angular distance to the agent's aim enabled the agent to learn its task far more efficiently. This sorting may help independently of architecture choice - i.e. you don't need to be using a RNN or CNN to see a benefit with this approach.</p>
  
  <p>Another thing worth considering, but probably not possible here because of the continuous feature <span class="math-container">$f_0$</span>, is whether you can invert the representation so that instead of being based on entities with properties, it is a view over property space populated with entities in certain positions. A CNN processed over a small enough "property space" instead of "entity space" may well perform better - this is why board game RL tends to treat the board positions as defining feature vector indexes which represent which entities are present on them, which is a very sparse structure that can represent far more states than ever occur in real games. The over-specified space works because it can be matched to architectures that generalise efficiently over it.</p>
  
  <p>In general, you need to consider different types of symmetry within the system - especially what is meaningful about the id number you have assigned to each entity. If the entity id is not meaningful, or is secondary to some other factor, you have some flexibility in changing the representation to make it meaningful and use architectures that take advantage of how you have injected that domain knowledge into the q function approximator. If the id is meaningful, think how could you best represent the difference between entities with different ids in your environment?</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-22T15:21:22.690Z
Answers.LastActivityDate: 2019-06-23T07:30:33.110Z
Answers.LastEditDate: 2019-06-23T07:30:33.110Z
Answers.UserDisplayName: Neil Slater
Body: <p>I am quite new to Deep Reinforcement Learning, and I'm trying to define states in a Reinforcement Learning problem. The environment consists of multiple identical elements, and each one of them is characterized by different features of the same type. In other words, let us say we have <span class="math-container">$e_0$</span>, <span class="math-container">$e_1$</span>, and <span class="math-container">$e_2$</span>. Then, suppose that each one is characterized by features <span class="math-container">$f_0$</span> and <span class="math-container">$f_1$</span>, where <span class="math-container">$f_0$</span> belongs to <span class="math-container">$[0, 1]$</span>, and <span class="math-container">$f_1$</span> belongs to <span class="math-container">$\{0, 1, 2, 3, 4, 5\}$</span>. Then, <span class="math-container">$e_0$</span> will have some value for the features <span class="math-container">$f_0$</span> and <span class="math-container">$f_1$</span>, and the same goes for <span class="math-container">$e_1$</span> and <span class="math-container">$e_2$</span>.</p>
  <p>How can I encode such states?</p>
  <p>Can I simply vectorize such state by concatenating the different features of each element obtaining <span class="math-container">$[f_{0e_0}, f_{1e_0}, f_{0e_1}, f_{1e_1}, f_{0e_2}, f_{1e_2}]$</span>, or should I use a convolutional architecture of some sort?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-06-22T07:34:17.123Z
Comments.Text: This can actually be a very tough problem that goes to the heart of limitations in function approximators (i.e. not directly related to RL). Given your description, I would assume that your problem is related to an environment that has multiple similar objects (e.g. playing cards, board game pieces, video sprites). If you want to ask about specifics for your problem, then this would be easier, please give more details about what each $e_n$ is and what $f_m$ represents - for instance if $f_0$ and $f_1$ are discrete positions in a finite space that has some potential solutions
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-06-22T07:50:27.610Z
Comments.Text: Exactly. The environment consists of multiple, very similar objects. Each of them has an upper bound for $f_0$, but we can make the simplifying - and not very limiting - assumption that for each $e_i$, $f_0$ belongs to $[0, 1]$. Each $e_n$ is basically a collection of these features. Substantially, $e_n$ defines an upper bound for $f_0$. Thanks for your interest in the question
Comments.UserDisplayName: Stencil
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-06-22T09:09:30.277Z
Comments.Text: Is it enough information for an answer or should I provide more?
Comments.UserDisplayName: Stencil
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-06-22T09:12:57.220Z
Comments.Text: It is probably enough. It depends whether you want a high level analysis in general, that might apply in broadly similar situations, or something more concrete for your specific environment. If it is the latter, then I suggest giving full details of what your features represent as their numerical ranges do not give much insight (although the fact that all state features are discrete is useful knowledge).
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-06-22T09:13:15.647Z
Comments.Text: A good answer is going to take some time to produce in either case.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-06-22T09:19:43.737Z
Comments.Text: I'd like a high level analysis, if possible. Thank you again!
Comments.UserDisplayName: Stencil
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-06-22T10:01:12.873Z
Comments.Text: Actually, $f_0$ is not discrete, as it belongs to $[0, 1]$, while $f_1$ is indeed discrete
Comments.UserDisplayName: Stencil
Tags: <reinforcement-learning><ai-design><deep-rl><markov-decision-process>
Title: How can I encode states where the environment consists of multiple identical elements, but each is characterised by different features?
UserDisplayName: Stencil
ThreadText: # How can I encode states where the environment consists of multiple identical elements, but each is characterised by different features?
  
  (Asked by: username_0 on 2019-06-22)
  
  I am quite new to Deep Reinforcement Learning, and I'm trying to define states in a Reinforcement Learning problem. The environment consists of multiple identical elements, and each one of them is characterized by different features of the same type. In other words, let us say we have $e\_0$, $e\_1$, and $e\_2$. Then, suppose that each one is characterized by features $f\_0$ and $f\_1$, where $f\_0$ belongs to $[0, 1]$, and $f\_1$ belongs to $\{0, 1, 2, 3, 4, 5\}$. Then, $e\_0$ will have some value for the features $f\_0$ and $f\_1$, and the same goes for $e\_1$ and $e\_2$.
  
  How can I encode such states?
  
  Can I simply vectorize such state by concatenating the different features of each element obtaining $[f\_{0e\_0}, f\_{1e\_0}, f\_{0e\_1}, f\_{1e\_1}, f\_{0e\_2}, f\_{1e\_2}]$, or should I use a convolutional architecture of some sort?
  
  **Tags:** reinforcement-learning, ai-design, deep-rl, markov-decision-process
  
  > **Comments:**
  > **username_1**: This can actually be a very tough problem that goes to the heart of limitations in function approximators (i.e. not directly related to RL). Given your description, I would assume that your problem is related to an environment that has multiple similar objects (e.g. playing cards, board game pieces, video sprites). If you want to ask about specifics for your problem, then this would be easier, please give more details about what each $e_n$ is and what $f_m$ represents - for instance if $f_0$ and $f_1$ are discrete positions in a finite space that has some potential solutions  
  > **username_0**: Exactly. The environment consists of multiple, very similar objects. Each of them has an upper bound for $f_0$, but we can make the simplifying - and not very limiting - assumption that for each $e_i$, $f_0$ belongs to $[0, 1]$. Each $e_n$ is basically a collection of these features. Substantially, $e_n$ defines an upper bound for $f_0$. Thanks for your interest in the question  
  > **username_0**: Is it enough information for an answer or should I provide more?  
  > **username_1**: It is probably enough. It depends whether you want a high level analysis in general, that might apply in broadly similar situations, or something more concrete for your specific environment. If it is the latter, then I suggest giving full details of what your features represent as their numerical ranges do not give much insight (although the fact that all state features are discrete is useful knowledge).  
  > **username_1**: A good answer is going to take some time to produce in either case.  
  > **username_0**: I'd like a high level analysis, if possible. Thank you again!  
  > **username_0**: Actually, $f_0$ is not discrete, as it belongs to $[0, 1]$, while $f_1$ is indeed discrete  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-06-22. Score: 1 | Accepted answer
  
  For general advice about state representation, you could check my answer to [How to define states in reinforcement learning?](https://ai.stackexchange.com/questions/7763/how-to-define-states-in-reinforcement-learning/7771#7771) - this does not cover your specific issue, but may help with other details such as whether to one-hot-encode and/or scale your discrete features. Also you will want to assess whether any state vector you construct actually contains *enough* data for reinforcement learning to work.
  
  Assuming that is all good, then your approach here:
  
  > Can I simply vectorize such state by concatenating the different features of each element obtaining $[f\_{0e\_0}, f\_{1e\_0}, f\_{0e\_1}, f\_{1e\_1}, f\_{0e\_2}, f\_{1e\_2}]$
  
  should work with a generic feed-forward neural network with two or more layers. As this is simple to construct, then it is a reasonable place to start just considering development time. If nothing else it can be a benchmark against other representations and model architectures that you may want to try.
  
  > should I use a convolutional architecture of some sort?
  
  That will depend on any structure inherent in your environment. The *interesting* thing about your description of the environment is the repetition of *meaning* in the values. Each entity $e\_i$ appears multiple times, and the units of feature $f\_{0e\_0}$ will be the same as $f\_{0e\_1}$.
  
  An unfortunate consequence of using a flattened vector is that the information about these repeated entities and their units is lost to the system. Any important details due to the entities being essentially the same of this must be "rediscovered" by the approximator training with many examples. Although neural networks can generalise function results, this does not apply to generalising across different parts of the input unless you choose an architecture designed to help with that.
  
  Typically you would use a RNN architecture (such as LSTM) if key information is in the *sequence order* of entities, or a CNN architecture if key information is in local patterns between neighbouring entities. By "key information" I mean whether useful relationship to a value function or optimal policy depends on those factors. This might be difficult to assess for some environments with mixed data types and complex meanings for the entity ids - so you may have to experiment with multiple architectures to figure out what factor is more important. However, it is also possible you have some insight based on known good policies, so can head more directly to a promising feature representation and architecture.
  
  Learning may benefit if instead of ordering your entities arbitrarily by identity in the vector, that you sort them according to some factor that is relevant to the goals of your agent. I have used this is in a colour matching environment where an agent had to hit a target with a "current" colour selection whilst avoiding incorrect colours - sorting target entities by whether they matched colour and then by angular distance to the agent's aim enabled the agent to learn its task far more efficiently. This sorting may help independently of architecture choice - i.e. you don't need to be using a RNN or CNN to see a benefit with this approach.
  
  Another thing worth considering, but probably not possible here because of the continuous feature $f\_0$, is whether you can invert the representation so that instead of being based on entities with properties, it is a view over property space populated with entities in certain positions. A CNN processed over a small enough "property space" instead of "entity space" may well perform better - this is why board game RL tends to treat the board positions as defining feature vector indexes which represent which entities are present on them, which is a very sparse structure that can represent far more states than ever occur in real games. The over-specified space works because it can be matched to architectures that generalise efficiently over it.
  
  In general, you need to consider different types of symmetry within the system - especially what is meaningful about the id number you have assigned to each entity. If the entity id is not meaningful, or is secondary to some other factor, you have some flexibility in changing the representation to make it meaningful and use architectures that take advantage of how you have injected that domain knowledge into the q function approximator. If the id is meaningful, think how could you best represent the difference between entities with different ids in your environment?
  
  
  ---
  
  