Concrete Example for Q Learning

Question

I am not sure if I understood the q learning algorithms correctly. Therefore I would give a concrete example and ask if someone can tell me how to update the q value correctly.

First I initialized a Neural Network with random weights. It shall henceforth evaluate the Q Value for all possible actions(4) given a State S.

Then the following happens. The agent is playing and is exploring. For 3 steps the Q Values evaluated were: (0,-1,-5,0), (0,-1,0,0), (0,-.6,0,0)

The reward given was: 0,0,1 The action took were: (1.,1.,1.) In the random walk example (same reward given), it was: (1.,2.,3.)

So what are the new Q - Values, assuming a discount factor of 0.99 and the learning rate 0.1?

The States for Simplicity are only one number: 1,1.3,2.4 Where 2.4 is the state who ends the game...

The same example holds for exploiting. Is the algorithm the same here?

Here you see my last implementation:

    public void rlearn(ArrayList<Tuple> tupels, double learningrate, double discountfactor) {

    //newQ = sum of all rewards you have got through
    for(int i = tupels.size()-1; i > 0; i--) {
        MLData in = new BasicMLData(45);
        MLData out = new BasicMLData(5);

        //Add State as in
        int index = 0;
        for(double w : tupels.get(i).statefirst.elements) {
            in.add(index++, w);
        }

        //Now start updating Q - Values 
        double qnew = 0;
        if(i <= tupels.size()-2){
            qnew = tupels.get(i).rewardafter + discountfactor*qMax(tupels.get(i+1));
        } else {
            qnew = tupels.get(i).rewardafter;
        }

        tupels.get(i).qactions.elements[tupels.get(i).actionTaken] = qnew;
        //Add Q Values as out
        index = 0;
        for(double w : tupels.get(i).qactions.elements) {
            out.add(index++, w);
        }
         bigset.add(in, out);
    }
}

Edit: This is the qMax - function:

    private double qMax(Tuple tuple) {
    double max = Double.MIN_VALUE;
    for(double w : tuple.qactions.elements) {
        if(w > max) {
            max = w;
        }
    }
    return max;
}

Answer 1

Most Deep Q-learning implementations I have read are based on Deep Q-Networks (DQN). In DQN, the q-value network maps an input state to a vector of q-values, one for each action:

$$ Q(s, \mathbf{w}) \to \mathbf{v} $$

where $s$ is the input state from the environment, $\mathbf{w}$ are the parameters of the neural network, and $\mathbf{v}$ is a vector of q-values, where $v_i$ is the estimated q-value of the ith action. In the Sutton and Barto book, the q-value function is written as $Q(s, a, \mathbf{w})$, which corresponds to the network output for action $a$.

Unlike tabular Q-learning, Deep Q-learning updates the parameters of the the neural network according to the gradients of the loss function with respect to the parameters. DQN uses the loss function

$$ L(\mathbf{w}) = [(r + \gamma max_{a'} Q(s', a', \mathbf{w^-})) - Q(s, a, \mathbf{w})]^2 $$

where $\gamma$ is the discount rate, $a$ is the selected action (either greedily or randomly for an $epsilon$-greedy behavior policy), $s'$ is the next state, $a'$ is the argmax action for the next state, and $\mathbf{w^-}$ is an older version of the network weights $\mathbf{w}$ that is used to help stabilize training.

In deep Q-learning, training directly updates parameters, not q-values. Parameters are updated by taking a small step in the direction of the gradient of the loss function

$$ \mathbf{w} \gets \mathbf{w} + \alpha [(r + \gamma max_{a'} Q(s', a', \mathbf{w^-})) - Q(s, a, \mathbf{w})] \nabla_w Q(s, a, \mathbf{w}) $$

where $\alpha$ is the learning rate.

In frameworks like tensorflow or pytorch the derivative is calculated automatically by giving the loss function and model parameters directly to an optimizer class which uses some variation of mini-batch gradient descent. In eagerly executed tensorflow updating the parameters for a mini-batch might look something like

batch = buffer.sample(batch_size)
observations, actions, rewards, next_obervations = batch

with tf.GradientTape() as tape:
    qvalues = model(observations, training=True)
    next_qvalues = target_model(next_obervations)
    # r + max_{a'} Q(s', a') for the batch
    target_qvalues = rewards + gamma * tf.reduce_max(next_qvalues, axis=-1)
    # Q(s, a) for the batch
    selected_qvalues = tf.reduce_sum(tf.one_hot(actions, depth=qvalues.shape[-1]) * qvalues, axis=-1)
    loss = tf.reduce_mean((target_qvalues - selected_qvalues)**2)

grads = tape.gradient(loss, model.variables)
optimizer.apply_gradients(zip(grads, model.variables))

Though I am not familiar with the Encog neural network framework you are using, based on the example Brain.java file from your Github repo and Chapter 5 of the Encog User Manual and the Encog neural network examples on Github it looks like weights are updated as follows:

1. A training set is constructed from pairs of input and target output.
2. A Propagation instance, train, is constructed with a network and training set. Different subclasses of Propagation use different loss functions to update the network parameters.
3. The method train.iterate() is called to run the network on the inputs, calculate the loss between the network outputs and target outputs, and update the weights according to the loss.

For DQN, a training set is constructed from a random sample from the experience replay buffer to help stabilize training. A training set could also be the trajectory of an episode, which is what the tupels argument in the example code of the question appears to be.

The input would be the statefirst member of each element of tupels. Since the network produces a vector of q-values, the target output must also be a vector of q-values.

The target output element for the selected action is $r + \gamma max_{a'} Q(s', a', \mathbf{w^-})$, In the example code of the question, this is

double qnew = 0;
if(i <= tupels.size()-2){
    qnew = tupels.get(i).rewardafter + discountfactor*qMax(tupels.get(i+1));
} else {
    qnew = tupels.get(i).rewardafter;
}
tupels.get(i).qactions.elements[tupels.get(i).actionTaken] = qnew

The target output elements for actions that were not selected should be $Q(s, b, \mathbf{w})$, where $b$ is one of the non-selected actions. This should have the effect of ignoring the q-values of non-selected actions by making the network output equal to the target output.

So what are the new Q - Values, assuming a discount factor of 0.99 and the learning rate 0.1?

Assuming you mean target outputs by the new Q - Values, and given the trajectory of actions, (1, 1, 1), and q-value vectors from the question, the concrete target outputs are (0, 0 + 0.99 * 0, -5, 0), (0, 0 + 0.99 * 0, 0, 0), and (0, 1 + 0, 0, 0).