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 implemented by NetworkX.

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.


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; 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.

  • $\begingroup$ 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. $\endgroup$ Commented Mar 31, 2022 at 16:58
  • $\begingroup$ Please, put your specific question in the title. "Normalisation of reward function" is not specific and it's also not a question. $\endgroup$
    – nbro
    Commented Apr 1, 2022 at 9:16


You must log in to answer this question.