Does reinforcement learning apply to this type of problem? My problem can be described as follows:

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?
 A: 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."
