A decision algorithm to choose what partner to use Background

I have a setup where I need to make an API call to a partner to initiate a financial transaction. I have multiple partners, and I need to choose which one to use each time a transaction needs to happen. The characteristics differentiating two partners are: 


if the transaction is accepted or not (acceptance)
the cost of the transaction (fee charged by the partner, assumed to be constant over time)
the speed of the transaction (assumed to be constant over timefor each partner)


The characteristics of a transaction are especially:


amount
currency
(several other factors such as the user's country, the payment method he chose, etc)


Additional info: the acceptance rate of a partner is subject to
   change arbitrarily over time.

.

Algorithm

As you probably guessed, I am currently thinking about solutions and algorithms that could be used to solve the following problem.


  Inputs:
  
  
  a transaction (with all its characteristics)
  the database of all transactions having ever happened, containing for each transaction
  
  
  the partner used
  the fee charged
  if the transaction was accepted or not
  
  
  
  Output: the best partner to use to execute the transaction.


Obviously, the first step is to define best. Do we value speed more than cost? Do we value the expected acceptance rate more than both the cost and speed? etc.

Another important aspect I mentioned earlier is that the acceptance of the same transaction by the same partner might change over time. This means that the algorithm should sometimes try a partner that is believed not to be currently the best just to be able to, for instance, check if a partner's acceptance rate has improved over time.

My question

I'm obviously not asking someone to write a magic algorithm solving that. I have a background of CS, but I am unsure about what algorithms and types of algorithms are usually used to solve this kind of problem. I would be grateful to be given some extra terminology (e.g. if this is a typical problem with a particular name in the domain) and resources to be able to dig into the problem.

Please don't hesitate to ask if something is unclear.

Thank you!

[Edit] After searching a bit more on the web, it seems that this problem has a lot in common with the multi-armed bandit problem. However I believe that the algorithms presented to solve this problem (e.g. UCB1) could be suboptimal in this context, because they wouldn't take into account the characteristics of a transaction and act as if the partner didn't take them into account.
Techniques developed for the multi-armed bandit problem might be useful for discovering the partner with the best acceptance rate and dealing with the changing acceptance rate over time.  Those techniques balance "exploration" (sending transactions to a partner as a way to learn more information about their acceptance rate) vs "exploitation (sending transactions to the partner with the highest acceptance rate, to make use of the information gained previously).  You'll probably be especially interested in the non-stationary bandit problem.