Body: <p>I am working on implementing an RL agent and I want to demonstrate its effectiveness over a bounded problem space. The setting is essentially a <a href="https://en.wikipedia.org/wiki/Queueing_theory#Queueing_networks" rel="nofollow noreferrer">queueing network</a> and so it can be represented as a graph. I want to consider the agent's performance over all graphs up to order <span class="math-container">$n$</span> and with average degree from <span class="math-container">$0$</span> (edgeless) to <span class="math-container">$n-1$</span> (fully connected).</p>
  <p>I have looked into generating random graphs using the Erdős–Rényi model, for example. My thought is that I could show the average performance of my agent for different settings of number of nodes and edge probability (under this particular graph generation model).</p>
  <p>Are there any established techniques that are along the lines of this approach?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-20T21:09:47.290Z
Comments.Text: It's not clear to me what you want to represent as a graph (and how exactly do you want to do it? i.e. what are the nodes and edges of this graph?), probably because I don't know what you mean by "queueing network". Moreover, what do you mean by "bounded problem space"? What is bounded here? Finally, I don't understand why you want to evaluate the agent's performance over all graphs? What graphs are you talking about?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-20T21:21:13.650Z
Comments.Text: Thanks for the link. But I think it would be helpful for those not familiar with queuing networks if you described more explicitly your state space, the action space (remember that, in RL, you typically assume that your problem/environment can be modelled as a Markov decision process? That's why I am asking this info), what RL algorithm you are using, and why your problem is bounded, and why this information is important.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-20T21:34:27.463Z
Comments.Text: I think the root of my question is independent of my particular MDP formulation. Say we forget the queueing network example and consider a grid world problem (which is probably more familiar to most). I can define a specific grid world instance, with some positive reward positions and some negative, and show that my agent does well most of the time when faced with this specific instance. What I am interested in is showing that my agent does well on many different grid world instances up to a certain grid size, and with various densities of positive and negative reward states.
Comments.UserDisplayName: hoffee
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-20T21:39:36.723Z
Comments.Text: I know someone that is working on a very similar problem. Unfortunately, I can't share with you the details. However, to answer your question "Are there many approaches trying to do a similar thing?", I would say "no", so you may want to investigate your own approaches or try something new.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><graph-theory>
Title: How can I evaluate a reinforcement learning algorithm over an entire problem space?
UserDisplayName: hoffee
ThreadText: # How can I evaluate a reinforcement learning algorithm over an entire problem space?
  
  (Asked by: username_0 on 2020-10-20)
  
  I am working on implementing an RL agent and I want to demonstrate its effectiveness over a bounded problem space. The setting is essentially a [queueing network](https://en.wikipedia.org/wiki/Queueing_theory#Queueing_networks) and so it can be represented as a graph. I want to consider the agent's performance over all graphs up to order $n$ and with average degree from $0$ (edgeless) to $n-1$ (fully connected).
  
  I have looked into generating random graphs using the Erdős–Rényi model, for example. My thought is that I could show the average performance of my agent for different settings of number of nodes and edge probability (under this particular graph generation model).
  
  Are there any established techniques that are along the lines of this approach?
  
  **Tags:** reinforcement-learning, graph-theory
  > **Comments:**
  > **username_1**: It's not clear to me what you want to represent as a graph (and how exactly do you want to do it? i.e. what are the nodes and edges of this graph?), probably because I don't know what you mean by "queueing network". Moreover, what do you mean by "bounded problem space"? What is bounded here? Finally, I don't understand why you want to evaluate the agent's performance over all graphs? What graphs are you talking about?  
  > **username_1**: Thanks for the link. But I think it would be helpful for those not familiar with queuing networks if you described more explicitly your state space, the action space (remember that, in RL, you typically assume that your problem/environment can be modelled as a Markov decision process? That's why I am asking this info), what RL algorithm you are using, and why your problem is bounded, and why this information is important.  
  > **username_0**: I think the root of my question is independent of my particular MDP formulation. Say we forget the queueing network example and consider a grid world problem (which is probably more familiar to most). I can define a specific grid world instance, with some positive reward positions and some negative, and show that my agent does well most of the time when faced with this specific instance. What I am interested in is showing that my agent does well on many different grid world instances up to a certain grid size, and with various densities of positive and negative reward states.  
  > **username_1**: I know someone that is working on a very similar problem. Unfortunately, I can't share with you the details. However, to answer your question "Are there many approaches trying to do a similar thing?", I would say "no", so you may want to investigate your own approaches or try something new.  
  
  ---
  
  ## 0 answers
  
  