Body: <h1>Problem</h1>
  <p>Currently, I have some problems defining a reward function for my RL project and mainly with how to normalise the score such that the highest possible score for all instances of the environment becomes 1. The main reason why this is important is that the highest possible score can differ highly between each instance. For example, in one instance, the maximal score can be 50, and in another instance, it can be 150. However, the maximal score is never known.</p>
  <h1>The environment</h1>
  <p>The environment of my agent is a single graph of a few thousand nodes, where the goal is to maximise the coverage of a set of <span class="math-container">$k$</span> cliques (cliques are subgraphs in which all the nodes are connected to all other nodes in the clique). Each state consists out of the current candidate clique set <span class="math-container">$D=\left \{C_1,\dots,C_{k} \right \}$</span> and a newly found clique <span class="math-container">$C_\text{found}$</span>, which means each state is a tuple of <span class="math-container">$s=\left (D, C_\text{found} \right)$</span>. The agent then decides if the newly found clique will replace another clique in the set, and so yes, which one. For instance, if the action is <span class="math-container">$5$</span>, then <span class="math-container">$C_\text{found}$</span> will replace the clique <span class="math-container">$C_5$</span> in the candidate clique set, and if the action is <span class="math-container">$k+1$</span>, it will replace none of the cliques in the candidate set. The cliques themself are found through the <a href="https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm" rel="nofollow noreferrer">Bron–Kerbosch algorithm</a> implemented by <a href="https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.clique.find_cliques.html#networkx.algorithms.clique.find_cliques" rel="nofollow noreferrer">NetworkX</a>.</p>
  <h1>The Reward Function</h1>
  <p>The simplest version of the reward function should be the new coverage of <span class="math-container">$D \in {s}'$</span>. The function below shows how this is calculated.
  <span class="math-container">$$
  R(s,a,{s}')=\left | \text{Cov}(D\in {s}') \right |, \\ 
  \text{where } \text{Cov}(D) = \bigcup_{C \in D}C
  $$</span>
  However, this reward function runs into the problem I described at the start of my question. Another reward function I experimented with is using the difference in coverage between the two states. This reward can be divided by the maximum clique in the graph, such that the score is normalised to a value between -1 and 1. The maximum clique can either be found through approximation or exactly by first going over all the cliques. Below is the formula of this reward function:
  <span class="math-container">$$
  R(s,a,{s}')=\frac{\left | \text{Cov}(D\in {s}') \right | - \left | \text{Cov}(D\in s) \right |}{\left | C_\text{maximum}\right |}
  $$</span>
  This reward function also runs into some problems. First off, in my current training setup, I have never seen the reward be either -1 or 1, with the highest value seen being around 0.75. This difference is caused by most cliques, especially the largest ones, overlapping with other cliques in the graph. The second issue is that with this reward function, the agent will converge to a local optimum in which it rarely changes cliques in the candidate clique set. Lastly, I believe a proper normalised version of the first reward function will work better because this function is also used in the comparison.</p>
  <h1>Neural architecture and RL algorithm</h1>
  <p>Currently, I am using PPO with a highly custom neural implementation, in which a GNN is used to first embed all the nodes at the start of the episode, and another GNN embeds all the cliques at each step. The embeddings of all the cliques are then combined and flattened such that I can use them as input for both the actor MLP and critic MLP. The code is written in PyTorch and PyTorch Geometric. I do not believe the network or the algorithm itself is the issue, but let me know if you think so.</p>
  <h1>Conclusion</h1>
  <p>I have tried looking at graph and node attributes, which I could use to normalise the coverage score, but I could not find anything. Recently, I have been looking into <a href="https://arxiv.org/pdf/1602.07714.pdf" rel="nofollow noreferrer">adaptive normalisation</a>; however, I am entirely new to this concept and would love to have some advice on it or get some links to implementations of it with PPO in PyTorch. Other advice about how to normalise this score function is also more than welcome. Also, if you need more information, just let me know.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-03-31T16:58:32.223Z
Comments.Text: I think your core problem is not reward normalisation, but lack of markov property in the state features. How are you representing the cliques in the state? The ids would be meaningless, and the number of nodes likewise. Potentially a binary vector of "in/not in set" might get close to markov trait, but it might not be enough. If the agent cannot assess the edge data or some proxy of it (perhaps from the algorithm you linked), then it will be very hard for it to track whether it could do better in future, and predict a final return. I don't think that goes away with normalisation.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-04-01T09:16:42.077Z
Comments.Text: Please, put your **specific question** in the title. "Normalisation of reward function" is not specific and it's also not a question.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><rewards><proximal-policy-optimization><reward-functions><normalisation>
Title: Normalisation of reward function
UserDisplayName: Jesse
ThreadText: # Normalisation of reward function
  
  (Asked by: username_0 on 2022-03-31)
  
  # Problem
  
  Currently, I have some problems defining a reward function for my RL project and mainly with how to normalise the score such that the highest possible score for all instances of the environment becomes 1. The main reason why this is important is that the highest possible score can differ highly between each instance. For example, in one instance, the maximal score can be 50, and in another instance, it can be 150. However, the maximal score is never known.
  
  # The environment
  
  The environment of my agent is a single graph of a few thousand nodes, where the goal is to maximise the coverage of a set of $k$ cliques (cliques are subgraphs in which all the nodes are connected to all other nodes in the clique). Each state consists out of the current candidate clique set $D=\left \{C\_1,\dots,C\_{k} \right \}$ and a newly found clique $C\_\text{found}$, which means each state is a tuple of $s=\left (D, C\_\text{found} \right)$. The agent then decides if the newly found clique will replace another clique in the set, and so yes, which one. For instance, if the action is $5$, then $C\_\text{found}$ will replace the clique $C\_5$ in the candidate clique set, and if the action is $k+1$, it will replace none of the cliques in the candidate set. The cliques themself are found through the [Bron–Kerbosch algorithm](https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm) implemented by [NetworkX](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.clique.find_cliques.html#networkx.algorithms.clique.find_cliques).
  
  # The Reward Function
  
  The simplest version of the reward function should be the new coverage of $D \in {s}'$. The function below shows how this is calculated.
  $$
  R(s,a,{s}')=\left | \text{Cov}(D\in {s}') \right |, \\
  \text{where } \text{Cov}(D) = \bigcup\_{C \in D}C
  $$
  However, this reward function runs into the problem I described at the start of my question. Another reward function I experimented with is using the difference in coverage between the two states. This reward can be divided by the maximum clique in the graph, such that the score is normalised to a value between -1 and 1. The maximum clique can either be found through approximation or exactly by first going over all the cliques. Below is the formula of this reward function:
  $$
  R(s,a,{s}')=\frac{\left | \text{Cov}(D\in {s}') \right | - \left | \text{Cov}(D\in s) \right |}{\left | C\_\text{maximum}\right |}
  $$
  This reward function also runs into some problems. First off, in my current training setup, I have never seen the reward be either -1 or 1, with the highest value seen being around 0.75. This difference is caused by most cliques, especially the largest ones, overlapping with other cliques in the graph. The second issue is that with this reward function, the agent will converge to a local optimum in which it rarely changes cliques in the candidate clique set. Lastly, I believe a proper normalised version of the first reward function will work better because this function is also used in the comparison.
  
  # Neural architecture and RL algorithm
  
  Currently, I am using PPO with a highly custom neural implementation, in which a GNN is used to first embed all the nodes at the start of the episode, and another GNN embeds all the cliques at each step. The embeddings of all the cliques are then combined and flattened such that I can use them as input for both the actor MLP and critic MLP. The code is written in PyTorch and PyTorch Geometric. I do not believe the network or the algorithm itself is the issue, but let me know if you think so.
  
  # Conclusion
  
  I have tried looking at graph and node attributes, which I could use to normalise the coverage score, but I could not find anything. Recently, I have been looking into [adaptive normalisation](https://arxiv.org/pdf/1602.07714.pdf); however, I am entirely new to this concept and would love to have some advice on it or get some links to implementations of it with PPO in PyTorch. Other advice about how to normalise this score function is also more than welcome. Also, if you need more information, just let me know.
  
  **Tags:** reinforcement-learning, rewards, proximal-policy-optimization, reward-functions, normalisation
  > **Comments:**
  > **username_1**: I think your core problem is not reward normalisation, but lack of markov property in the state features. How are you representing the cliques in the state? The ids would be meaningless, and the number of nodes likewise. Potentially a binary vector of "in/not in set" might get close to markov trait, but it might not be enough. If the agent cannot assess the edge data or some proxy of it (perhaps from the algorithm you linked), then it will be very hard for it to track whether it could do better in future, and predict a final return. I don't think that goes away with normalisation.  
  > **username_2**: Please, put your **specific question** in the title. "Normalisation of reward function" is not specific and it's also not a question.  
  
  ---
  
  ## 0 answers
  
  