Reinforcement Learning (Q Learning)

Question

I was reading a paper on traffic flow optimization using Multi-Agent Q learning. the paper proposes the following method: Deploy a Reinforcement learning controller at each intersection with traffic lights.

first the Q value equation is:

$Q^{t}(s,a) = (1- \alpha )Q^{t-1}(s,a) + \alpha (R{t} + \gamma max_{a}(Q^{t-1}(s,a))$

second the state is: the sum of vehicle queues lengths at the current intersection and one hop intersections

third the action space is:

here the actions represent the possible moves of vehicles at the intersection.

forth the reward at time t is

$R^{t} = -( w_1\sum q_{current intersection} + w_2\sum q_{neighbors} )$

where the q refers to vehicle queues lengths, w1 and w2 are constants.

fifth there is the algorithm in the image below where it acquires the action required for maximizing the Q value

What I am trying to understand is, the reward calculation does not take an action as a parameter. How does it choose an action properly.

I am a newbie to reinforcement learning, so please if you find my question naive, cosedire referring me to a proper textbook. Thanks

Answer 1

What I am trying to understand is, the reward calculation does not take an action as a parameter. How does it choose an action properly.

The reward function does not choose the action. It gives the immediate consequences for your previous action - and in most cases is a consequence of all previous actions, states and random factors in the environment. Although it should only depend on most recent state, previous action plus a random factor at most.

In your case reward depends directly on the resulting state = how many cars at each junction after taking an action, and not directly on the previous action = which traffic flow to enable. It does still depend on the action indirectly, via however the environment works. But that does not need to be expressed mathematically (as a model of the system) for Q learning to work. Although not stated, the reward probably also depends on a random factor outside of your control = how many cars turn up at each junction.

It is the Q value which eventually ranks the different actions and allows you to select the best action. The value $Q^t(s, a)$ gives you the current best estimate for future rewards (for a continuous problem, such as yours, it is common to have a discount factor, $\gamma$, to give more weight to immediate rewards).

There are multiple ways to select the next action in reinforcement learning, depending on the problem, your learning algorithm etc. In the example pseudo-code you copied, the selection process is using Upper Confidence Bound (or UCB), which is a relatively sophisticated way of balancing exploration of actions that might be better than your current best estimate, versus simply using the "best" action so far. If you always took the "best" action, in many cases this would cause a problem because you would never update your knowledge of what the other actions do.

One of the standard textbooks for all this is Sutton & Barto, Reinforcement Learning: An Introduction. The notation in that book is slightly different to what you have used, but it explains the concepts involved in your problem in easy-to-understand detail.