Reinforcement Learning with long term rewards and fixed states and actions
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.