5
$\begingroup$

The Q function uses the (current and future) states to determine the action that gets the highest reward.

However, in a stochastic environment, the current action (at the current state) does not determine the next state.

How does Q learning handle this? Is the Q function only used during the training process, where the future states are known? And is the Q function still used afterwards, if that is the case?

$\endgroup$
  • 2
    $\begingroup$ Could you clarify: "In a stochastic environment, where the action doesn't influence state" - do you mean that the state is not 100% predictable, and the action doesn't fully determine the state? E.g. deciding to move forward, and a game then moves you 1d6 steps forward. Or do you really mean that the action choice has absolutely no influence on the resulting state - and the state will evolve by rules independent of the action choice? E.g. deciding to buy or sell, getting some reward, then the state just changes randomly. The answer you need is very different depending on which case you mean. $\endgroup$ – Neil Slater Mar 31 '18 at 12:20
  • 1
    $\begingroup$ @NeilSlater, Thanks for your response. In this case the action has no influence at all on the next state. The state will evolve by rules independent of the action choice. $\endgroup$ – redlum Apr 2 '18 at 19:00
  • 2
    $\begingroup$ In which case, although Q learning should work without errors, you would be expending resources for the agent to learn the fact that the action does not influence state. Your situation is more commonly known as "contextual bandit" and there a variety of solvers out there. The positive news is that good old supervised learning should be fine to learn from the historical data. Then it's just a matter of how online your algorithm needs to be, and how risk averse whilst making online decisions. $\endgroup$ – Neil Slater Apr 2 '18 at 19:11
2
$\begingroup$

How does Q learning handle this? Is the Q function only used during the training process, where the future states are known? And is the Q function still used afterwards, if that is the case?

The learned $Q$-function is not only used during training, but also after training (in what we may call "deployment", when we expect a trained agent to behave according to what it has learned).

However, the reliance on future states is only there during training, it is no longer required for deployment.

During training, we use the following $Q$-learning update rule:

$$Q(s, a) \gets (1 - \alpha) Q(s, a) + \alpha \left( R + \gamma \color{red}{\max_{a'} Q(s', a')} \right),$$

where $s'$ is the state we reach after executing $a$ in $s$. Here, the $\color{red}{\text{red}}$ part is the part where we rely on knowledge of the future $s'$. This is available in training because we can simply pick $a$, execute it in $s$, observe $s'$, and only then trigger our update step.


Outside of training (and actually also during training), we also rely on our $Q(s, \cdot)$ function for the selection of actions. We typically select an action $a$ according to $a = \arg\max_a Q(s, a)$; we select the action $a$ that maximises $Q(s, a)$ in our current state $s$. The important thing to note here is that there is no $s'$ term in this description of how we select actions: we do not require knowledge of our future state.


Note: in my answer I decided to answer the question literally as it is written, i.e. I'm explaining how $Q$-learning can still work in the described setting where actions $a$ have no influence whatsoever on the future state reached.

In practice, I would never recommend actually using $Q$-learning in such a setting, and instead refer to Neil Slater's comment about Contextual Multi-Armed Bandit algorithms likely providing a better solution.

$\endgroup$
1
$\begingroup$

A simple example would make sense. The state of the system is the sensorinput received by the robot, for example the lightcolor on the underground which can be white or black (line following task). The action are the commands to the actuator which can be “left” and “right”. The q-table is a mapping between sensordata and control-commands. And a concrete q-table is called a policy, because he brings the robot on top of the black line. Will this setup work, will the q-learning algorithm finds after a while the error minimum and drives the robot precisely on the line? Unfortunately not, because q-learning is not a method for programming robots, it is more the proof of how agent-programming can be teached at the university.

But, calling the idea wrong or not working, doesn't hit the point. Because the state-action-pair model is fundamental for gaming-theory. It is one of the most powerful techniques out there. To use it for something meaningful we must adapt it according to the “Learning from demonstration” approach. That means, in the demonstration task, the decision of a human expert are recorded in the q-table. For example, if the human is controlling the robot to the left, if the line is left from the robot, this will be recorded in the q-table. So the q-table is used as a memory for the agent. And this episodic memory is used in a later modul for generating decisions to drive the robot autonomously.

In recent literature the concept is called “Episodic control” and is described in the paper Learning to Play Visual Doom using Model-Free Episodic Control The q-table is used as an buffer for each action. And the current sensor input is the search parameter for access the buffer. The question in the OP was, how can the q-learning algorithm handle an environment in which future states are unknown. The answer is, that the agent replays previous experiences, that means it works like an opening book in computerchess without searching the future gametree.

$\endgroup$
  • $\begingroup$ The Q-function is not a mapping between sensordata and control-commands, as you state. A Q-function is a mapping from states and actions to a value (or real number), which represents the expected return. Also, you use rather confusing terminology, such as "a concrete q-table", which you mean a policy derived from the $Q$-function. However, if someone is not very familiar with RL, your terminology will confuse him or her. Furthermore, a lot of information in this answer is misleading and out of context. $\endgroup$ – nbro Jul 13 at 21:34
  • $\begingroup$ Indeed, my answer wasn't the best one. To my excuse, it was written a long time ago and it contains perhaps some older information. The Qlearning table is at foremost a probability of transition which follow up state will happen, if the agent executes an action, P(s'|s, a). The example for line following robot is: if line is left and action is left then line is middle with 90%. $\endgroup$ – Manuel Rodriguez Jul 13 at 22:32

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.