Which solutions are there for RL agents when not all actions are always available?
You could use an out-of-the-box learning algorithm if the availability of actions is deterministic and depends only on the state the agent is in, i.e. if availability of actions does not violate the Markovian assumption.
You need only substitute the full action space with the 'available action space' in any place where the action space shows up.
As an example, consider the update rule in Q learning, then replace the Q(S,A) with Q(S, A') where S' indicates the available actions for that particular S.
Please note that the referenced paper targets a setting in which availability of actions is not Markovian.