Is it really hard to learn in a stochastic environment?

Question

I understand that a stochastic environment is one that does not always lead you to the desired state by giving a particular action $a$ (But the probability to change to a not desire state is fixed, right?).

For example, the frozen lake environment is a stochastic environment. Sometimes you want to move in one direction and the agent slips and moves in another direction. Unlike an environment with multiple agents that the probability of the actions of the other agents is changing because they keep learning (a non-stationary environment).

Why is it difficult to learn in a stochastic environment, if, for example, Q-learning can solve the frozen lake environment? In what cases would it be difficult to learn in a stochastic environment?

I have found some articles that address that issue, but I don't understand why it would be difficult if Q-learning can solve it (for discrete states/actions).

Answer 1

A stochastic environment does not necessarily mean that the reward distribution is stationary. It can be, as in the case of FrozenLake. The paper you linked also mentions that other algorithms already addressed the non-stationary case.

If you have a simple stationary stochastic environment, then you just need more sample trajectories to determine which action is better. If the environment is fully observable, then based on the estimated action values you can build a deterministic optimal policy.