Consider the following problem.
We have a process, that generates $N$ stones (e.g. 2000) in one batch $b$. Every pebble has state $s_{i}^b$ and reward $s_i^b$. After choosing one pebble $i$ from the $N$, we start sampling again using the chosen pebble as a starting point and we generate the next batch $b+1$. The state $s_i^b$ is a vector of real-values and the reward $r_i^b$ is a real value.
The problem is to choose pebbles so that we maximize reward $r_i^b$ in long term. Because depending on how we choose the pebble, we can sample around the region that gives a better or worse reward $r$.
During each new batch, we make one selection of one pebble (so actions can from $i, \dots, N$. We have access to the previous $m$ batches (e.g. through replay buffer) with their rewards and states.
In short, it looks like this:
- Chose randomly the first pebble from which we start sample;
- We start sampling from the chosen pebble in the current batch;
- We sample $N$ pebbles from a process, each pebble have a state $s_i^b$ and reward $r_i^b$;
- We can chose one pebble from $i \dots N$ as action $a_i^b$ based on state $s_i^b$ and reward $r_i^b$;
- Go to point 1 and repeat;
For example, at the moment, I choose in a given batch $b$ pebble with max reward $r_i^b$, so
$$i = \underset{i}{\mathrm{argmax}}\, r_i^b$$ and then use $a_i^b$ for a the current batch $b$.
But what I want is to choose: $$i = \underset{i}{\mathrm{argmax}}\, \underset{b}{E}[R_i^b | s_i, a_i]$$
Graphically speaking:
Assuming one Batch (N) is 30 P - pebble, P - chosen pebble
batch 1: PPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
batch 2: PPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
batch 3: PPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
batch 4: PPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
batch 5: PPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
So, if I have a batch $N$, when I choose one element from the batch as an action, so the expected reward is the highest in long term, and start the sampling again from it. So only one element per batch can be chosen. And only choice of the one pebble per batch does affect the sequence in the next batch, but not inside the current batch.
The problem is, what Reinforcement Learning algorithm to use, when we choose only one item from N. And the one choice affect the whole sampled sequence in the next batch. For example in batch 1 to 4, the reward can be very low, and in batch 5 the reward is super high, if we chose wisely the pebbles in 4 previous batchs.