Q learning in a stochastic environment

Question

Most examples I have seen about Q learning, are performed in a deterministic world. For example, in the traditional grid world, the agent can finally do the path searching by exploring and exploiting the environment with a reward function without knowing the transition probability function.

$$Q(s,a) = Q(s,a) + a*[ Reward + discount * Max Q(s',a') - Q(s,a)] $$

Now suppose the grid is a stochastic environment, an agent can move up/left/right with 1/3 probability. How can I program the Q learning, does that mean that in calculating the $Max Q(s',a')$,
$$Max Q(s',a') = Max [ P(up)*Q(s',up) , P(left) *Q(s',down) , P(right) * Q(s, right)]?$$

Answer 1

Q-learning also permits an agent to choose an action stochastically (according to some distribution). In this case, the reward is the expected reward given that distribution of actions. I think this fits your case above.

Q-learning also permits actions that may fail. Hence, $Q(s, Left)$ might lead you to a state $s'$ that is not the to the left $s$ (e.g. the action "fails" with some probability). In that case, the model (MDP, table of Q-values, automaton) will encode the possibility of failure directly and no distributions or expected values are needed.

Answer 2

Actually there is no exploration done in calculating the Q-value as you described it above. Exploration happens only if you introduce a certain probability with which a random action is performed. Calculating the Q-value only enables to choose the action maximizing the Q-value given the current state.

In effect, this means choosing the state-action pair $(s, a) $ with the highest Q-value such that $s $ is the current state and $a $ is one of the possible actions.

Transition probabilities are considered implicitly, as the Q-value adapts to those transitions that actually happen--whether intentionally chosen or randomly selected via exploration or the stochastic environment. As Tim mentioned, you can also choose actions probabilistically. In the best case, however, this is as good as deterministically choosing the maximum.

Answer 3

Actually, no assumption is made Q-learning regarding the transition function other than that it exists and is a probability distribution. The definition of a Q-function is given by $$Q(s, a) = \mathbb{E}_{\tau \sim (\pi, p)}[r(s, a) + \gamma v_\pi(S') | S_t=s, A_t=a]\;$$ where $v_\pi$ is the value function of policy $\pi$, and $\tau$ is the trajectory which we assume to be generated according to the policy $\pi$ and transition function $p$.

What this essentially means is that the Q-function is the expected (discounted) returns of taking action $a$ in state $s$ and following $\pi$ thereafter to generate the rest of the trajectory until termination. Now, $\pi$ is used to generate actions whilst the transition function $p$ determines the state transition dynamics, i.e. it gives us $p(s' | s, a)$ (that is, the probability of transitioning to state $s'$ given that we took action $a$ in state $s$).

You can see that this definition, as I stated at the beginning of the answer, makes no underlying assumptions about whether or not $p$ is stochastic or deterministic.

Now suppose the grid is a stochastic environment, an agent can move up/left/right with 1/3 probability.

What you are describing here is not totally clear (at least to me), but I would not describe this as an instance of a stochastic environment. A clearer example would be that, if the action 'up' is taken, then with probability $x$ the agent actually moves up, and with probability $1-x$ the agent moves instead to the right (for some $x \in (0, 1)$).