Reinforcement Learning with long term rewards and fixed states and actions I have read a lot about RL algorithms, that update the action-value function at each step with the currently gained reward. The requirement here is, that the reward is obtained after each step.

I have a case, where I have three steps, that have to be passed in a specific order. At each step the agent has to make a choice between a range of actions. The actions are specific for each step.

To give an example for my problem:
I want the algorithm to render a sentence of three words. For the first word the agent may choose a word out of ['I', 'Trees'], the second word might be ['am', 'are'] and the last word could be chosen from ['nice', 'high']. After the agent has made its choices, the reward is obtained once for the whole sentence.

Does anyone know which algorithms to use in this kind of problem?



To give a bit more detail on what I already tried:

I thought that using value iteration would be an reasonable approach to test. My problem here is that I don't know how to assign the discounted reward for the chosen operations.

For example after the last choice I get a reward of 0.9. But how do I update the value for the first action (choosing out of I and Trees in my example)?
You don't need to have a reward on every single timestep, reward at the end is enough. Reinforcement learning can deal with temporal credit assignment problem, all algorithms are designed to work with it. Its enough to define a reward at the end where you, for example, give a reward of 1 if sentence is satisfactory or -1 if it isn't. Regular tabular Q-learning would easily solve the toy problem that you gave as an example.