9
$\begingroup$

I am trying to understand reinforcement learning and markov decision processes (MDP) in the case where a neural net is being used as the function approximator.

I'm having difficulty with the relationship between the MDP where the environment is explored in a probabilistic manner, how this maps back to learning parameters and how the final solution/policies are found.

Am I correct to assume that in the case of Q-learning, the neural-network essentially acts as a function approximator for q-value itself so many steps in the future? How does this map to updating parameters via backpropagation or other methods?

Also, once the network has learned how to predict the future reward, how does this fit in with the system in terms of actually making decisions? I am assuming that the final system would not probabilistically make state transitions.

Thanks

$\endgroup$
4
$\begingroup$

In Q-Learning, on every step you will use observations and rewards to update your Q-value function:

$$ Q_{t+1}(s_t,a_t) = Q_t(s_t,a_t) + \alpha [R_{t+1}+ \gamma \underset{a'}{\max} Q_t(s_{t+1},a') - Q_t(s_t, a_t)] $$

You are correct in saying that the neural network is just a function approximation for the q-value function.

In general, the approximation part is just a standard supervised learning problem. Your network uses (s,a) as input and the output is the q-value. As q-values are adjusted, you need to train these new samples to the network. Still, you will find some issues as you as using correlated samples and SGD will suffer.

If you are looking at the DQN paper, things are slightly different. In that case, what they are doing is putting samples in a vector (experience replay). To teach the network, they sample tuples from the vector, bootstrap using this information to obtain a new q-value that is taught to the network. When I say teaching, I mean adjusting the network parameters using stochastic gradient descent or your favourite optimisation approach. By not teaching the samples in the order that are being collected by the policy the decorrelate them and that helps in the training.

Lastly, in order to make a decision on state $ s $, you choose the action that provides the highest q-value:

$$ a^*(s)= \underset{a}{argmax} \space Q(s,a) $$

If your Q-value function has been learnt completely and the environment is stationary, it is fine to be greedy at this point. However, while learning, you are expected to explore. There are several approaches being $\varepsilon$-greedy one of the easiest and most common ways.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you this is very useful, that makes a lot of sense! Just to clarify, once the system has been trained, would you simply feed each possible action with the current input states to the neural network and select the action which estimates the largest reward (q-value)? $\endgroup$ – CatsLoveJazz Feb 24 '16 at 10:42
  • 1
    $\begingroup$ Correct. However, keep in mind that if you environment is not stationary you may want to keep some exploration going on. In general, Q-learning runs online and you continuously train. $\endgroup$ – Juan Leni Feb 24 '16 at 11:09
  • $\begingroup$ Great, are you aware of any literature surrounding your answer? I guess an alternative to online training would be to retrain on newly observed data every n time periods in order to not let failed exploration affect performance in a production environment. $\endgroup$ – CatsLoveJazz Feb 24 '16 at 13:04
  • 1
    $\begingroup$ I am basically referring to the exploration-exploitation dilemma. There many approaches.. An easy to apply one is here: tokic.com/www/tokicm/publikationen/papers/… where you adaptively adjust epsilon based on the error of your value function $\endgroup$ – Juan Leni Feb 24 '16 at 13:21
  • 1
    $\begingroup$ A classic are this paper / book (1996): web.mit.edu/people/dimitrib/NDP_Encycl.pdf. athenasc.com/ndpbook.html Nowadays there is a lot of work combining Deep Neural Networks and RL. Deepmind papers are a good example: storage.googleapis.com/deepmind-data/assets/papers/… $\endgroup$ – Juan Leni Feb 24 '16 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.