Reinforcement learning with uniformly random dynamics

Question

Suppose I have an MDP $(S, A, p, R)$ where the $p(s_j|s_i,a_i)$ is uniform, i.e given an state $s_i$ and an action $a_i$ all states $s_j$ are equally probable.

Now I want to find an optimal policy for this MDP. Can I just apply the usual methods like policy gradients, actor-critic to find the optimal policy for this MDP? Or is there something I should be worried about?

At least, in theory, it shouldn't make any difference. But I'm wondering are there any practical considerations I should be worried about? Should the discount factor, in this case, be high?

The reward function here depends both on states and actions and is not uniformly random.

Answer 1

When the next state selection is not driven by any meaningful dynamics i.e. it is independent of starting state $s$ and action taken $a$, but the rewards received do depend somehow on the $s$ and $a$, then the MDP you describe also fits with something called a Contextual Bandit Problem where there is no control over state due to action choice, and thus no incentive to choose actions other than for their potential for immediate reward.

Any algorithm capable of solving a full MDP can also be put to use attempting to solve a contextual bandit problem, as the MDP framework is a strictly more general case of the contextual bandit problem, and can model such an environment. However, this is typically going to be inefficient, as MDP solvers make no assumptions about state transition dynamics and need to experience and learn them. Whilst if you start with an algorithm designed to solve a contextual bandit problem, you have the assumption of randomised state built in to the algorithm, it does not need to be learned, and the learning process should be more efficient.

Alternatively, if you only have RL solvers available, you can reduce variance and get the same effective policy by setting discount factor, $\gamma = 0$.

If for some reason you still want or need a long-term discounted value prediction from your policy, you can take the mean predicted value of some random states (or even of all the states if there are few enough of them) and multiply by $\frac{1}{1-\gamma}$ for whatever discount factor you want to know it for. Or if predicting for a time horizon, just multiply by number of steps to the horizon.

Answer 2

Convergence guarantees for basic RL algorithms like policy gradient / actor-critic methods make no assumptions about the dynamics of the MDP. So, theoretically, you don't need to change much.

Practically, when the number of possible trajectories from any given state is so high, the return from each state will have high variance. This means you'll have to collect much more experience for your estimates of expected return to converge to their true values. Intuitively, an environment with high uncertainty requires the agent to do more knowledge-gathering to behave optimally.

My real advice to you depends on what exactly you're trying to do. If you want to have the kind of agent that could learn to behave well in an extremely random environment, then all you need to worry about is giving it enough experience to learn from.

(Your agent should also take a little longer before deciding it's "confident" in its evaluation of different states. That is, don't behave greedily before you're sure your estimates are accurate. Explore adequately. This advice is only relevant if your MDP dynamics aren't actually completely uniform.)

If, however, you want to train an RL agent specifically to solve a problem formulated as an MDP with uniformly random dynamics, then I would tell you to not waste your time. We know before spending the computation that all policies would be equally good/bad in this setting. Since actions are irrelevant to the environment, it would be inefficient to deploy an RL agent that will only learn that which action it takes doesn't matter.

---

As noted in the comments, the last paragraph is only true when reward from each state-action pair $(s,a)$ is also uniformly random. If it is not, just being aware of the high variance and giving your agent a lot of experience should do the trick.