One way you can definitely approach the problem is by using (Deep) Reinforcement Learning (DRL).
YouTube is actually using DRL as well to suggest videos to users in order to maximize users' engagement with their website. For more information (and further references to papers explaining how other major companies implement their recommendation systems), see this paper. Just as a bit of motivation.
Other research into that direction could be found here.
Actually, there are different DRL algorithms available and each might be suitable for approaching the problem you described above from a slightly different angle.
The way how I would roughly approach your problem is as follows:
As I understand it, the goal is the following.
You want to show either of four messages to a user (only one at a time) and always display the message, which is expected to reduce some metric (=conversion time), to the user.
In that case, an DRL algorithm, or agent, could directly be trained on minimizing the conversion time without having to explicitly produce conversion time estimates per message & user. That might make phrasing the problem at hand much easier (in terms of modelling the learning task).
The outcome of training an DRL agent consists of a so-called optimal policy network, which dictates the agent which message to display to a given user, upon observing the provided user data, such that conversion time gets minimized for that user. The aforementioned network is a simple artificial Neural Network (NN) or Recurrent NN (RNN).
Training the DRL agent will consist of two steps being repeated many times in alternating order.
One step will include the sampling/generation of training data.
For this step, the algorithm (initially being untrained) will be applied to the problem at hand and predict messages for given users. Then, (in addition to the provided user data that was fed as input to the agent) each user's response (i.e. the conversion time) is recorded. This can later be used as the reward that the agent receives for having selected the selected message given the provided user data. Here, a low conversion time translates to a high reward.
In the second step, the agent's policy network will be trained in order to make the agent's predictions more accurate in the next round of generating training data. Here, the data recorded during the previous step will be used.
How the policy network is optimized largely depends on which DRL algorithm you choose. The range of different methods varies vastly. Some algorithms try to estimate utilities (i.e. measures of goodness) per action given a certain state (here, state = provided user data used to generate a prediction). In this case, an action would be choosing message A or choosing message B etc. A popular algorithm implementing this procedure is Deep Q-Learning.
However, if you rather want to predict probabilities per action, then Proximal Policy Optimization might rather be what you are looking for.
Upon convergence, i.e. stabilization of the goal metric (=convergence time per user), the algorithm has arrived at its optimal policy (ideally speaking).
The only drawback with this approach is that DRL usually requires quite a lot of training. But maybe you are lucky and pre-trained recommendation system models exist.
If there is still anything unclear, feel free to ask in the comments.