My problem can be described as follows:

Problem description

In my problem, the state does not influence the observations seen by the agent, but the state decides the rewards for the agent. So, the agent has to do its best to get more rewards, but it can't influence the observations. Does reinforcement learning apply to such problems?

Imagine multiple shelves / racks where boxes of various sizes can be stored. A shelf can store 10 boxes of size 1 or 5 boxes of size 2 or 2 boxes of size 4 and 1 box of size 2 and so on. Given historical logs of insert and remove box requests, can we use RL to find the best location to place a box given the current openings in all the shelves? The goal is maximize storage and reduce small openings int he shelves because small boxes are rare. Can the algorithm take into account the historical insert and remove patterns?

  • $\begingroup$ Do you mean that the agent cannot measure the state directly? And what is the use for the observations, if they are independent from the rest of the system? $\endgroup$ – Jacques Jun 24 '16 at 21:48
  • $\begingroup$ The agent can see the state fully, but the observations are not dependent on the state $\endgroup$ – gnjago Jun 24 '16 at 22:34
  • $\begingroup$ That doesn't quite address @Jacques' question: If the agent can fully observe state, what purpose do the observations serve? $\endgroup$ – Sean Easter Jun 24 '16 at 22:37
  • $\begingroup$ The inputs comes from outside the system. The agent has to operate on the input to maximize reward from the state. The input / observation is independent of the state. $\endgroup$ – gnjago Jun 24 '16 at 23:12
  • $\begingroup$ But what does depend on the observation? $\endgroup$ – Sean Easter Jun 24 '16 at 23:42

In general yes, reinforcement learning can reason about agents who lack full knowledge of their environment, namely through partially observable Markov decision processes (POMDPs). These generalize MDPs by adding a set $\Omega$ of observations and set $O$ of probabilities of observations, conditioned on state and action.

Where in a normal MDP state is deterministically known, POMDPs reason about probabilistic belief across the state space. (You could think of an agent's belief in an standard MDP as $1$ for the state the agent is in, $0$ else.)

(To learn more about this class of problems, you might consult lesson 10 of the udacity & Georgia Tech RL course.)

That said, in the terminology of MDPs, your problem is fully observed. Think of the single shelf in your example as a binary string of length $10$, with values of $1$ if the space is filled, $0$ else. You can now represent your state space as a tuple of this string, the length of the box in the queue (or null if none), and the address of a box to remove (or null if none).

At any given time step, you know where all the boxes are on the shelves, and you know the size of the box you need to place. When you place that box, you know deterministically where it goes, and which binary values to flip to $1$. Given a remove action, you know which values to flip to $0$.

What you don't know is whether you'll get a remove or place command, and what size the next place. An MDP accounts for this uncertainty in the transition function $T(s,a,s')$, which gives the probability of winding up in a state $s'$ after taking action $a$ in state $s$.

Some methods model the transition function explicitly; others learn without representing $T$. Which is best is another question, and in either case you'd need a reward function that could formalize "maximize storage."

  • $\begingroup$ In POMDP, the state influences the observations. It seems to me that your answer doesn't correspond to the author's situation. The wikipedia indicates that the observations are conditional on the state and action. Unless, maybe, you consider the reward as what the wikipedia calls 'observations'. $\endgroup$ – Jacques Jun 24 '16 at 21:45
  • $\begingroup$ Cheers @Jacques, I think I just misread the initial question. Updated following edits by OP. $\endgroup$ – Sean Easter Jun 25 '16 at 16:37
  • $\begingroup$ Thanks. There are multiple shelves. So use multiple strings to represent state? If I train with 25 shelves for example, can I learn in a generic way such that its generalised to any number of shelves and any size per shelf? $\endgroup$ – gnjago Jun 29 '16 at 5:36
  • $\begingroup$ I can't think offhand of a fully generalized way to learn this, from the RL methods I'm familiar with. I can think of a few ways that you might be able to use prior learning on simpler versions to speed learning of larger problems. I'll give it more thought and give an answer to your other question. (Apologies, didn't see the comment on that one until now.) $\endgroup$ – Sean Easter Jun 29 '16 at 14:41

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.