Non-differentiable reward function to update a neural network

In Reinforcement Learning, when reward function is not differentiable, a policy gradient algorithm is used to update the weights of a network. In the paper Neural Architecture Search with Reinforcement Learning they use accuracy of one neural network as the reward signal then choose a policy gradient algorithm to update weights of another network.

I cannot wrap my head around the concept of accuracy as a non-differentiable reward function. Do we need to find the function and then check if it is mathematically non-differentiable?

I was wondering if I can use another value, for example silhouette score (in a different scenario) as the reward signal?

• I do not understand your question. It doesn't usually matter in RL whether a reward function is differentiable with respect to any parameters or not. Are you asking about why that is the case? Are you asking why accuracy is a non-differentiable function? Do you have a specific problem to solve (NN to train) and want to use the same approach as in the paper? – Neil Slater Jun 9 '20 at 21:13
• I am asking if I can use silhouette score as a reward signal to update a network (a simple Multi-layer Perceptron) by policy gradient. I want to know if is this is correct according to what policy gradient is used for. – samsambakster Jun 10 '20 at 6:02
• OK, that makes sense. Can you explain "I can not wrap my head around the concept of accuracy as a non-differentiable reward function." more - what is the issue here? Is it that you think accuracy is differentiable? – Neil Slater Jun 10 '20 at 7:55
• So, accuracy is a number. What do we consider as a non-differentiable is the formula for accuracy here? how can I think about it mathematically? – samsambakster Jun 11 '20 at 7:38
• The part of accuracy that is non-differentiable is the comparison operator for whether the prediction equals the ground truth or not. That does not have any meaningful gradient, and it only acts on point values (typically discrete set $\{0,1\}$), so does not have any regions over which gradient can be measured (unlike e.g. ReLU). So any attempt to figure out gradients of parameters that caused a specific accuracy value will fail when they reach that step. – Neil Slater Jun 11 '20 at 8:40

I cannot wrap my head around the concept of accuracy as a non-differentiable reward function. Do we need to find the function and then check if it is mathematically non-differentiable?

In reinforcement learning (RL), the reward function is often not differentiable with respect to any learnable parameters. In fact it is quite common to not know the function at all, and apply a model-free learning method based purely on sampling many observations of state, action, reward and next state. For reward, you don't need to know the reward function as a function of your parameters, but you do need to know how to caclulate it from each observation. That means that the reward is either provided as part of the environment, or it is clear how to calculate it from the initial state, action or next state. In the case of an agent that creates a neural network then reports the accuracy, you can probably view the NN training process and its results including accuracy on a validation set as a "black box" that reports back an arbitrary reward signal.

In Reinforcement Learning, when reward function is not differentiable, a policy gradient algorithm is used to update the weights of a network

Policy gradient methods are one broad family of RL methods which are also often model-free. Alternatively, value-based methods are broadly the other choice (e.g. Q-learning) or can be used in combination with policy gradient methods (e.g. Actor-Critic). All of these can be model-free, and often are.

Unless you want to apply a model-based RL method, then you have no need to find the reward function in an explicit form based on any parameters. Even if you did want to use a model-based approach, the reward function does not need to be differentiable.

I was wondering if I can use another value, for example silhouette score (in a different scenario) as the reward signal?

Yes this would likely be viable, and could be made to work similarly to the paper, provided there is some meaningful connection between the parameters you manipulate and the end result.

RL can be made to work as a generic way of optimising numeric measure influenced due to a vector of parameters. That includes indirect optimisation of neural networks by non-differentiable metrics such as accuracy. There is nothing special about the choice of accuracy here, the metric just needs to be related to the parameters being learned.

There is a catch. Indirect learning using RL can produce very noisy training data, due to e.g. covariance between all the parameters, and it can take many samples to get a clear gradient signal through all the noise and make meaningful updates. It can be inefficient compared to other optimisation methods if they are available - however, the ability to extract a gradient for the parameters even when rules are complex and non-differentiable is a nice feature of RL.