As far as I understood, most RL applications have much more states than there are actions to choose from.
Yes, this is quite common, but in no way required by the underlying theory of Markov Decision Processes (MDPs). The most extreme version of the opposite thing - with one state (or effectively no state, as state is not relevant) - are k-armed bandit problems, where an agent tries to find a single best long-term action in general from a selection of actions. These problems typically would not use RL algorithms such as Q-learning or policy-gradients. However, that is partly because they are described with different goals in mind (e.g. minimising "regret" or simply gaining as much reward as possible during the learning process), and RL algorithms will work to solve them, albeit less efficiently than algorithms designed to work on bandit problems directly.
I am thinking about using RL for a problem where I have got a lot of actions to choose from, but only very few states.
That should work, provided your problem is still a MDP. That means for instance that the state evolves according to rules depending on which action was taken in which starting state. If the state evolution is instead arbitrary or random, then you may have a contextual bandit problem instead.
There is an important difference here between:
- a large number of entirely different actions, each with different results, which need enumeration and have to be explored separately
and
- a large action space due to measurable values which are part of an action, such as how much force to apply in a motor
The former will require lots of exploration, since any specific combination of action and state could be the ideal. With the latter, you can use that fact that numerical values that are similar will often give similar results, which will make generalisation via function approximation (e.g. neural networks) work efficiently in your favour.
The algo should render (for whatever reason) a sentence with three words. I always want to have a sentence with three words, but I have many words to choose from. After choosing the words, I get some sort of reward
This seems more like the first bullet-point above, although that may depend if a natural language model could be applied for example. E.g. if "This is good" and "This is great" would produce similar rewards in a specific state, then there is maybe some benefit to generalisation, although I am not quite sure where you would fit this knowledge - possibly in a generator for a sentence vector as the "raw" action and then have a LSTM-based language model produce the actual action from that vector, similar to seq2seq translation models.
Are RL algorithms an efficient way to solve this?
Yes, but whether or not it is the most efficient will depend on other factors, such as:
Whether the environment is stochastic or deterministic with regard to both reward and state progression.
Whether state progression is key to obtaining the best rewards in the long term (e.g. there is some "goal" or "best" state that can only be reached by a certain route).
What the actual size of the MDP is $|\mathcal{S}| \times |\mathcal{A}|$. Small MDPs can be fully enumerated, allowing you to estimate action values in a simple table. If you have 10 states and 1,000,000 discrete actions, with no real pattern of actions mapping to results, then a big 10 million entry table will actually be reasonably efficient.
Competitive algorithms to RL here might be global search and optimisation ones, such as genetic algorithms. The more arbitrary and deterministic your environment is, the more likely it is that an exhaustive search will find your optimal policy faster than RL.
I am thinking about using policy gradients with an ε-greedy algorithm to explore a lot of the possible actions before exploiting the knowledge gained.
This should be fine. Exploration here is definitely important, but finding the sweet spot for the right amount of it will be hard, and depend on other traits of the environment.
You may want to use something like upper confidence bound action selection or simply optimistic initial values, in order to ensure exploration does not miss certain actions. An epsilon greedy approach will miss a certain fraction of actions over time, and the expectation of that fraction grows smaller progressively more slowly, so it may be possible to miss an important action for a long time if you rely on being able to randomly select it.
To give a handy example: The algo should render (for whatever reason) a sentence with three words. I always want to have a sentence with three words, but I have many words to choose from. After choosing the words, I get some sort of reward.
I would consider modelling this as sequences of 3 actions, each of which chooses a word, with the state being a start token (whatever the state you already have) plus the sentence so far, and on every 3 words the environment is consulted to reset the state to the next start token and to gather a reward (rewards for interim steps would be zero).
Doing this immediately makes the state space much larger than the action space, as your state includes history of up to two actions. If you had 10 different start states, and 100 word choices, then your state space would be 101,010 and action space 100.
This will fit available designs of RL algorithms, and allow for learning some internal language modelling if it is relevant. It will reduce your need to model sentence construction outside of the agent. Most importantly, if "good" or "bad" sentences tend to start or end with certain words, and you use function approximation, then the algorithm may discover combinations more efficiently than iterating over all sentences as if they were completely independent.
