# Reinforcement Learning (and specifically REINFORCE algorithm) for one-round "games"

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?

This seems like a multi-armed bandit problem (no states involved here). I had the same problem some times ago and I was advised to sample the output distribution M times, calculate the rewards and then feed them to the agent, this was also explained in this paper Algorithm 1 page 3 (but different problem & different context). I honestly don't know if this will work for your case. You could also take a look at this example.

• The multi-armed bandit problem seems very different from my problem except for the statelessness. The Neural knapsack seems relevant, but it's under a pay wall Apr 29 '20 at 15:22
• sorry, what do you mean ? Apr 29 '20 at 20:36
• What do I mean where? Apr 30 '20 at 10:06
• "but it's under a pay wall" ? Apr 30 '20 at 12:35

I think the key to your problem may not the one-round. Use RL to solve the knapsack problem is great related to the topic rl for combination optimization. U can use NEURAL COMBINATORIAL OPTIMIZATION WITH REINFORCEMENT LEARNING to get some idea and find more related solutions.

You should look into contextual bandits, and specifically gradient bandit solvers (see section 13).

Your derivation of the gradient seems correct to me. Instead of a sampled/bootstrapped value function (as in Actor-Critic) or sampled full return (in REINFORCE) you can use the sampled reward. You will probably want to subtract a baseline from $$v$$, e.g. a rolling average reward for the current policy.

I have successfully used a gradient bandit solver for one-shot optimisation problem with 5000 dimension actions. It was not as strong as a custom optimiser or SAT solver, but whether or not that is an issue for you will depend on the problem.

Besides contextual Bandit or multi-armed Bandit perspective, if you want to use a dataset to train RL policy, I would recommend you Batch RL, it is another RL working in a supervised learning way to train a policy.

For your problem, I think you can still use one-state trajectories to train REINFORCE. For example, there is a trajectory, $$\tau={(s, a, r, s^{\prime})}$$, there $$s^{\prime}$$ is NULL. By using REINFORCE, you can get the gradient $$\theta = \theta + \alpha \nabla_{\theta}log \pi_{\theta}(a|s)r$$, and you do not need $$s^{\prime}$$ here.