1
$\begingroup$

As part of data science course I would like to solve particular problem with reinforcement learning algorithm.

I believe I understand general concept, however the problems I had read about up till now had no random factor included. I would like to ask if it's valid to assume that reinforcement learning algorithm will be able to find "good" (somewhat close to optimal) solution when, at each step, one or more random events can occur, provided that we know the probability of those events?

For practical example that I can think of: let's say we have to find exit from labyrinth as quick as possible, on each turn we can decide to rest or move. If we move, we become more tired, which increases probability that we will fall and twist our ankle (if this happens our speed is reduced for several turns). We know what's the probability of falling on each turn, but we do not know if this will really happen or not. During rest we reduce probability of falling.

In my project I would like to include several (around 5) of such random events.

Is it correct to assume that reinforcement learning algorithm should be able to find a valid solution, despite such random factors? We can define "valid" as, for example, in 90% of cases taking less than X turns. If yes, I would highly appreciate if you could point me in right direction, or to any materials describing practical solutions to such problems.

Thank you in advance for your input and sorry in case this question is really basic (hopefully not)!

$\endgroup$
1
  • 1
    $\begingroup$ I suggest you to check en.wikipedia.org/wiki/Multi-armed_bandit. Random factors are inherent to this problem, and you must maximize the expected gain while taking randomness into account. $\endgroup$
    – user114966
    Mar 12 at 4:55
2
$\begingroup$

Yes, in general reinforcement learning algorithms can handle random events in the environment. Think about the q-learning update rule $$ Q(s_t,a_t)= Q_{s_t, a_t} + \alpha \left(r_{t+1} + \gamma max_aQ(s_{t+1},a)\right) $$ But remember $$Q(s_{t+1},a) = \mathbb{E}_\pi\left( \sum_{i=t+2}^T\gamma^{i-1}r_{i} \right)$$ that is the expected value of the discounted sum of future rewards. This handles randomness in the environment quite well and eventually the value will adjust to factor in these random events. In a tabular environment this will always converge to the optimal value function and corresponding policy.

If you know the environment dynamics (which it seems like you do here) $$ p\left(s', r\mid s,a\right)$$ you can use a dynamic programming method like policy iteration or value iteration to efficiently compute an optimal policy and value function. I recommend looking at the first 4 chapters of Reinforcement Learning: An Introduction by Sutton and Barto (at least chapters 3 and 4). The text is available freely online on their website at their website.

$\endgroup$

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.