Body: <p>I am trying to build an RL agent to solve the NP-hard problem graph coloring. The problem is quite challenging. </p>
  
  <p>This how I addressed it.</p>
  
  <h3>The environment</h3>
  
  <p>To preserve the scalability of the algorithm, providing the agent with the whole graph wouldn't be a good idea. Therefore, the input for the agent would be a window of embeddings.</p>
  
  <p>More precisely, first, I would apply an embedding to the graph to generate fixed-size vectors to every vertex in the graph (thus, every vertex in the graph is represented as a vector that contains some information about its neighborhood and position in the graph).</p>
  
  <p>Second, the agent will get a window of the embedding. For example, when coloring vertex number <span class="math-container">$17$</span>, the input would be the <span class="math-container">$2n$</span> vectors from vertex <span class="math-container">$17-n$</span> to <span class="math-container">$17+n$</span>, to give the agent more local information.</p>
  
  <p>Third, I think the agent would require more information about the number of colors already used and the number of the already colores vertices.</p>
  
  <h3>The agent</h3>
  
  <p>My biggest problem is how the agent should be. Technically, the problem is the action space dimension. For a given graph, the maximal number of colors is the number of vertices which varies from graph to graph (losing the scalability). Plus, the possible actions at each state varies with the history of the coloring. The possible colors for a given state (or node) are all the used colors eliminating the connected colors and adding the possibility of a new color, that is, for vertex <span class="math-container">$56$</span>, the agent has already used the first <span class="math-container">$40$</span> colors <span class="math-container">$\{0, 1, 2, 3, \dots,40 \}$</span>, and node <span class="math-container">$56$</span> is connected to some neighbors already colored with <span class="math-container">$\{14, 22, 40 \}$</span>, the possible colors are <span class="math-container">$\{0,1, \dots, 40 \}- \{14, 22, 40 \} + \{41\}$</span>.</p>
  
  <p><em>How do I overcome the high dimensional inconsistent action space?</em></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-26T12:52:19.873Z
Comments.Text: I'm fairly sure most problems with a large option for inputs simply inputs it as an image through a convnet, so I think that would certainly be step in the right direction. That being said, no one has ever actually "solved" any NP hard problem, so i wouldn't expect much no matter what network you use. You might be able to achieve something that gives some solution, just perhaps not the optimum.
Comments.UserDisplayName: Recessive
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-26T13:18:57.693Z
Comments.Text: Sure. I'm trying to find an approximation for the solution. Plus, the possible set of actions depend on the whole history of coloring not only the state. So, there are actually two big problems: the high dimensional action space comparing to the low dimension of possible actions, and the set of possible action depends an all previous state not only the current.
Comments.UserDisplayName: Ahmed Rebei
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-27T00:27:14.147Z
Comments.Text: I would think a recursive net, probably an LSTM, with modified hidden states that are computed through a convnet. This architecture should be capable of remembering previous states and analysing the high dimensional nature of the input (each dimension can be used as a channel into the convnet) while also providing a low dimensional output.
Comments.UserDisplayName: Recessive
Tags: <reinforcement-learning><ai-design>
Title: Coloring graphs with reinforcement learning
UserDisplayName: Ahmed Rebei
ThreadText: # Coloring graphs with reinforcement learning
  
  (Asked by: username_0 on 2019-07-26)
  
  I am trying to build an RL agent to solve the NP-hard problem graph coloring. The problem is quite challenging.
  
  This how I addressed it.
  
  ### The environment
  
  To preserve the scalability of the algorithm, providing the agent with the whole graph wouldn't be a good idea. Therefore, the input for the agent would be a window of embeddings.
  
  More precisely, first, I would apply an embedding to the graph to generate fixed-size vectors to every vertex in the graph (thus, every vertex in the graph is represented as a vector that contains some information about its neighborhood and position in the graph).
  
  Second, the agent will get a window of the embedding. For example, when coloring vertex number $17$, the input would be the $2n$ vectors from vertex $17-n$ to $17+n$, to give the agent more local information.
  
  Third, I think the agent would require more information about the number of colors already used and the number of the already colores vertices.
  
  ### The agent
  
  My biggest problem is how the agent should be. Technically, the problem is the action space dimension. For a given graph, the maximal number of colors is the number of vertices which varies from graph to graph (losing the scalability). Plus, the possible actions at each state varies with the history of the coloring. The possible colors for a given state (or node) are all the used colors eliminating the connected colors and adding the possibility of a new color, that is, for vertex $56$, the agent has already used the first $40$ colors $\{0, 1, 2, 3, \dots,40 \}$, and node $56$ is connected to some neighbors already colored with $\{14, 22, 40 \}$, the possible colors are $\{0,1, \dots, 40 \}- \{14, 22, 40 \} + \{41\}$.
  
  *How do I overcome the high dimensional inconsistent action space?*
  
  **Tags:** reinforcement-learning, ai-design
  
  > **Comments:**
  > **username_1**: I'm fairly sure most problems with a large option for inputs simply inputs it as an image through a convnet, so I think that would certainly be step in the right direction. That being said, no one has ever actually "solved" any NP hard problem, so i wouldn't expect much no matter what network you use. You might be able to achieve something that gives some solution, just perhaps not the optimum.  
  > **username_0**: Sure. I'm trying to find an approximation for the solution. Plus, the possible set of actions depend on the whole history of coloring not only the state. So, there are actually two big problems: the high dimensional action space comparing to the low dimension of possible actions, and the set of possible action depends an all previous state not only the current.  
  > **username_1**: I would think a recursive net, probably an LSTM, with modified hidden states that are computed through a convnet. This architecture should be capable of remembering previous states and analysing the high dimensional nature of the input (each dimension can be used as a channel into the convnet) while also providing a low dimensional output.  
  
  ---
  
  ## 0 answers
  
  