I'm interested about using Reinforcement Learning in a setting that might seem more suitable for Supervised Learning. There's a dataset $X$ and for each sample $x$ some decision needs to be made. Supervised Learning can't be used since there aren't any algorithms to solve or approximate the problem (so I can't solve it on the dataset) but for a given decision it's very easy to decide how good it is (define a reward).
For example, you can think about the knapsack problem - let's say we have a dataset where each sample $x$ is a list (of let's say size 5) of objects each associated with a weight and a value and we want to decide which objects to choose (of course you can solve the knapsack problem for lists of size 5, but let's imagine that you can't). For each solution the reward is the value of the chosen objects (and if the weight exceeds the allowed weight then the reward is 0 or something). So, we let an agent "play" with each sample $M$ times, where play just means choosing some subset and training with the given value.
For the $i$-th sample the step can be adjusted to be: $$\theta = \theta + \alpha \nabla_{\theta}log \pi_{\theta}(a|x^i)v$$ for each "game" with "action" $a$ and value $v$.
instead of the original step: $$\theta = \theta + \alpha \nabla_{\theta}log \pi_{\theta}(a_t|s_t)v_t$$ Essentially, we replace the state with the sample.
The issue with this is that REINFORCE assumes that an action also leads to some new state where here it is not the case. Anyway, do you think something like this could work?