How to train a logical XOR with reinforcement learning?

Question

After reading an excellent BLOG post Deep Reinforcement Learning: Pong from Pixels and playing with the code a little, I've tried to do something simple: use the same code to train a logical XOR gate.

But no matter how I've tuned hyperparameters, the reinforced version does not converge (gets stuck around -10). What am I doing wrong? Isn't it possible to use Policy Gradients, in this case, for some reason?

The setup is simple:

• 3 inputs (1 for bias=1, x, and y), 3 neurons in the hidden layer and 1 output.
• The game is passing all 4 combinations of x,y to the RNN step-by-step, and after 4 steps giving a reward of +1 if all 4 answers were correct, and -1 if at least one was wrong.
• The episode is 20 games

The code (forked from original and with minimal modifications) is here: https://gist.github.com/Dimagog/de9d2b2489f377eba6aa8da141f09bc2

P.S. Almost the same code trains XOR gate with supervised learning in no time (2 sec).

Answer 1

Reinforcement learning is used when we know the outcome we want, but not how to get there which is why you won't see a lot of people using it for classification (because we already know the optimal policy, which is just to output the class label). You knew that already, just getting it out of the way for future readers!

As you say, your policy model is fine - a fully connected model that is just deep enough to learn XOR. I think the reward gradient is a little shallow - when I give a reward of +1 for "3 out 4" correct and +2 for "4 out of 4", then convergence happens (but very slowly).

Answer 2

There is some confusion between reinforcement and convergence in this question.

The XOR problem is of interest in a historical context because the reliability of gradient descent is identity (no advantage over an ideal coin toss) for a single layer perceptron when the data set is are the permutations representing the Boolean XOR operation. This is an information theory way of saying a single layer perceptron can't be used to learn arbitrary Boolean binary operations, with XOR and XAND as counterexamples where convergence is not only not guaranteed but productive of functional behavior only by virtue of luck. That is why the MLP was an important extension of the perceptron design. It can be reliably taught an XOR operation.

Search results for images related to deep reinforced learning provide a survey of design diagrams representing the principles involved. We can note that the use case for a reinforcement learning application is distinctly different from that of MLPs and their derivatives.

Parsing the term and recombining to produce the conceptual frameworks that were originally combined to produce DRL, we have deep learning and reinforcement learning. Deep learning is really a set of techniques and algorithmic refinements for the combination of artificial network layers into more successful topologies that perform useful data center tasks. Reinforcement learning is

Sutton states in his slides for the University of Texas (possibly there to get away from the Alberta winters), "RL is learning to control data." His is an overly broad definition, since MLPs, CNNs, and GRU networks all learn a function which is controlling data processing when the learned parameters are then leveraged in their intended use cases. This is where the perspective of the question may be based on the misinformative nature of these excessively broad definitions.

The distinction of reinforced learning is the idea that a behavior can be reinforced during use. There may be actual parallel reinforcement of beneficial behavior (as in more neurologically inspired architectures) or learning may occur in a time slicing operating system and share the processing hardware with processes that use what is learned (as in Q-learning algorithms and their derivatives).

Some define RL as machine learning technique that direct the selection of actions along a path of behavior such that some cumulative value of the consequences of actions take is maximized. That may be an excessively narrow definition, biased by the popularity of Markov processes and Q-learning.

This is the problem with the perspective expressed in the question. An XOR operation is not an environment through which a path can be blazed.

If one were to construct an XOR maze, where the initial state is undefined and the one single action is to fall into either the quadrant 10 or 01, it is still not representing an XOR because the input was not a Boolean vector

$\vec{B} \in \mathbb{B}^2 \; \text{,}$

and the output is not a 1 or 0 resulting from XOR operation, as would be the case for a multilayer perceptron learning of XOR operation. There is no cumulative reward. If there was no input and the move was to divide in half and chose both 10 or 01 because their reward was higher than 00 or 11, then that might be considered a reinforcement learning scenario, but it would be an odd one.

That the described setup leads to, "Getting stuck," is no surprise when the tool is a wrench for the turning of a screw.

If the design looses the reinforcement and the artificial network is reduced to a two layer perceptron, the convergence will be guaranteed given a labeled data set of sufficient size or an unsupervised arrangement where the loss function is simply the evaluation of whether the result is XOR.

To experiment with reinforced learning, the agent must interact with the environment and make choices that have value consequences that direct subsequent behavior. Boolean expressions are not of this nature, no matter how complex.

Answer 3

Maybe Deep Reinforced Learning?

I am not sure but AND gate could be solved by your implementation. I have other feeling with OR gates. Just think - first we need to have information about two conditions and then we can check for complex solutions. First of all I thought about Neural Network with one hidden layer. Sounds perfect.

I think you will understand when you check this Tensorflow-Keras code:

iterations = 50

model = Sequential()
model.add(Dense(16, input_shape=(None, 2), activation='relu')) # our hidden layer for OR gate problem
model.add(Dense(2, activation='sigmoid'))
model.summary()
opt = Adam(0.01)
model.compile(optimizer=opt, loss='categorical_crossentropy', metrics=['acc'])
# mean_squared_error categorical_crossentropy binary_crossentropy

for iteration in range(iterations):
    x_train = np.array([[0, 0], [0, 1], [1, 0], [1, 1]]) # table of inputs
    y_train = np.array([[1, 0], [0, 1], [0, 1], [1, 0]]) # outputs in categorical (first index is 0, second is 1)

    r = np.random.randint(0, len(x_train)) # random input
    r_x = x_train[r]
    r_x = np.array([[r_x]])
    result = model.predict(r_x)[0] # predict
    best_id = np.argmax(result) # get of index of "better" output

    input_vector = np.array([[x_train[r]]])
    isWon = False
    if (best_id == np.argmax(y_train[r])):
        isWon = True # everything is good
    else:
        # answer is bad!
        output = np.zeros((2))
        output[best_id] = -1
        output = np.array([[output]])
        loss = model.train_on_batch(input_vector, output)

    print("iteration", iteration, "; has won?", isWon)

When "answer" of agent is good - we are not changing anything (but we could train network with best action as 1 for stability).

When answer is bad, we set action as bad - other actions have more probability for be chosen.

Sometimes learning need to have more than 50 iterations but it is only my proposition. Play with hidden layer neuron count, learn rate and iterations.

Hope will help you :)