具有非平稳奖励的随机多路径路由问题：构建PayU的动态路由

17070具有非平稳奖励的随机多路径路由问题：构建PayU的动态路由0Pankaj Trivedi PayUPayments Pvt. Ltd.pankaj.trivedi@payu.in0Arvind Singh PayUPayments Pvt. Ltd.arvind.singh@payu.in0摘要0PayU的支付交易引擎每天通过多个支付网关处理数百万笔交易。通过适当的支付网关路由交易对于引擎来说至关重要，以优化可用性和成本。问题在于每个交易需要选择K个可用支付网关之一，其特征是未知的概率奖励分布。网关的奖励是其健康和成本因素的组合。只有当交易由网关处理时，即通过其成功或失败，才能实现网关的奖励。动态路由的目标是在一定的交易生命周期内最大化累积预期奖励。为了做到这一点，动态切换系统需要获取关于网关的信息（探索），同时通过选择最佳网关来优化即时奖励（利用）；由于这种权衡而付出的代价被称为遗憾。主要目标是最小化遗憾并最大化奖励。基本思想是根据网关成为最佳网关的概率选择一个网关。0路由问题是强化学习（RL）问题的直接表述。在RL问题中，代理与动态、随机和不完全已知的环境进行交互，目标是找到一种行动选择策略或策略，以优化某个长期性能度量。实验证明汤普森抽样算法接近最优。0关键词0机器学习，强化学习，路由问题0ACM参考格式：Pankaj Trivedi和ArvindSingh。2018年。具有非平稳奖励的随机多路径路由问题：构建PayU的动态路由。在WWW'18Companion：2018年Web会议伴侣，2018年4月23日至27日，法国里昂。ACM，纽约，纽约，美国，第4篇，6页。https://doi.org/10.1145/3184558.319163001 引言0PayU是一个支付网关聚合器，与多个能够处理在线信用卡支付的支付网关集成。PayU还与在线销售产品和服务的商家进行集成。每个与PayU集成的支付网关0本文发表在知识共享署名4.0国际（CC BY4.0）许可下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW'18 Companion，2018年4月23日至27日，法国里昂©2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可发布。ACM ISBN978-1-4503-5640-4/18/04。https://doi.org/10.1145/3184558.31916300平台在某一时间点上成功进行交易的概率未知（图1）。对于企业来说，能够将交易路由到适当的支付网关非常关键，以最大化成功交易的概率。这可以被建模为一个路由问题，其中必须为每个交易选择适当的支付网关，以最大化整体成功率。每个支付网关处理成功交易的成本是已知但不同的。每个网关的成本因素增加了另一个优化维度。直观地应用强化学习技术来从已处理交易的结果反馈中学习。学习进一步用于为每个交易推荐适当的网关。02 相关工作和修改0本文的方法是多臂赌博机问题的一种修改。在多臂赌博机（MAB）问题中，赌徒需要在每一轮游戏中选择 K个臂之一，每个臂都有一个未知的奖励分布。只有在选择一个臂时才能观察到奖励的实现，赌徒的目标是在给定的游戏时段 T内最大化他的累积预期收益。自从它们问世以来，各种修改的MAB问题在统计学、经济学、运筹学和计算机科学中得到了广泛研究，并用于模拟众多不确定性下的动态优化问题；例如临床试验（[3]），战略定价（[17]），创新投资（[18]），数据包路由（[19]），在线拍卖（[7]），组合选择（[20]）和在线广告（[21]）等。本文重点研究了一种MAB的形式，它允许奖励中存在广泛的时间不确定性，同时保持数学可行性。奖励中的不确定性是由于交易失败的各种原因引入的。公式中的另一个变化是由于开发必须偏向于最近的历史，因此需要对各个网关的成本变化进行修改。业务需要各种控制开关来平衡成功率和成本之间的权衡。上述要求已通过显著修改的技术实现。03 问题建模0设 χ  =  { 1 , ..., K }  为网关集合。设 Γ  =  { 1 ,  2 , ..., T  }表示推荐系统面临的决策时刻序列。在任何时刻 t  ∈  Γ，推荐系统会选择 K 个网关中的一个。当一个交易通过网关处理时0Track: 社交感知与企业智能  朝着智能企业转型 WWW 2018，2018年4月23日至27日，法国里昂E[R(T)] = ET�t=1(µ∗t − µtk)(3)217080图1：各个网关预期奖励的变化实例0k  ∈  χ  ，在时刻  t  ∈  Γ  ，根据交易处理结果获得奖励  X t k ∈ [0 ,  1 ] ，其中  X t k 是一个具有期望值 µ t k =  E [ X t k ] (1)的随机变量0我们用 µ � t 表示决策时刻 t 的最佳预期奖励 µ � t =  max k  ∈ χ µ tk (2)0目标是在时间 T内最大化预期总奖励。更方便的是，使用等效的预期总遗憾度量：由于在每一步中没有选择最优网关而导致的损失量。那么在时间 T内的预期总遗憾度量为04 解决方案 4.1 强化学习0强化学习是一类方法，其中控制系统要解决的问题是以回报（代表奖励或惩罚）来定义的。系统的目标是随着时间的推移最大化获得的回报。因此，对于期望行为给予高回报，对于不期望行为给予低回报。系统在选择策略以最大化获得的回报时在其动作序列中没有限制。实际上，系统必须找到自己解决给定任务的方法。图2显示了强化系统的块图，显示了控制器与其环境之间的基本交互。回报函数是固定的，传感器和执行器也是固定的，它们实际上是控制系统关注的环境的一部分。控制系统是学习根据状态输入 x 最大化回报 r而产生控制动作 a 的自适应部分。0图2：强化学习系统0该算法从一个无知状态开始，一无所知，并通过测试系统来获取数据。随着获取数据和结果，它学习到了最好和最差的行为方式（在本例中，它学到了哪个网关是最好的）。0环境0在我们的交易路由问题中，环境是各种网关当前可能的批准率，在任何给定时间点都是未知的。因此，环境是非稳态的，非稳态环境意味着旧信息可能不太相关，因为底层奖励可能发生变化。例如，如果两小时前一个支付网关的批准率为80％，那么该网关当前可能已经关闭，批准率为零。0奖励0每个交易，一旦尝试了一个合格的网关，就会产生成功或失败的结果，这通过支付函数转化为奖励。0推荐者0控制系统对每个交易充当推荐者。推荐者以一组合格的网关作为输入，并根据其迄今为止学到的环境状态，回应最佳网关来处理交易。0反馈0处理交易后获得的奖励被馈送到控制系统，以获得环境的新状态。系统中发起的任何交易都会要求支付网关的推荐，然后使用推荐的网关尝试交易，试验的结果作为奖励馈送到学习算法中，例如，如果交易成功，则被视为网关的奖励为1，如果交易失败，则奖励为0。这种安排被称为伯努利安排，因为奖励只有0和1。学习算法通过反馈循环进行学习，并试图最大化成功。0主题：社交感知与企业智能 朝着智能企业转型 WWW 2018年4月23日至27日，法国里昂The underlying problem is to know when to explore and exploitwhile selecting the gateway. Exploring means that we try a newgateway in hopes that the probability of rewards is higher even if itscurrent reward probability is not the best. Exploitation means thatwe continue selecting the best performing gateway. Exploitationis the right thing to do to maximize the expected reward in thegiven transaction, but exploration may produce the greater totalreward in the long run. If a gateway is not producing successfultransactions very often and we haven’t sampled it too much thenprobability of success is low but our confidence in the estimateis low too, so let’s give it a small chance in future. However, if agateway has processed too many transactions already and doinggood, our confidence in the estimate is also high, so let’s give ahigher chance of being recommended.To handle the problem of exploration and exploitation we usedBeta Distribution. We used Beta Distribution for following conve-nient reasons.(1) Beta distribution can have values between 0 and 1, whichis nice for our use case to represent probability of successand failure of the gateway. In general, it can present thetransactional health of the gateway.(2) When the prior is a Beta distribution and the likelihood is aBernoulli distribution, the posterior is also a Beta distribu-tion.(3) The update formula for determining the posterior only in-volves addition and subtraction, whereas for other distribu-tions it can be more complicated.The Beta distribution has 2 parameters, α and β, which govern itsshape. We refer to a specific distribution as Beta(α,β)Initially, we set α =1 and β =1. This results in a uniform dis-tribution, i.e. we assume nothing about our chances of winningâĂŞ all probabilities of winning are equally likely. This is called aminimally informative prior.A fat distribution means more “exploration”. A sharp distributionmeans more “exploitation” (if it has a relative high transactionhealth). Note that as the programmer, you don’t choose whetheror not to explore or exploit. You sample from the distributions,meaning it is randomly decided whether you should explore orexploit. Essentially the decision is random, with a bias towardgateways who have proven themselves to be more healthy.Beta(α, β) : prob(x|α, β) = xα−1(1 − x)β−1B(α, β)(4)B(α, β) =10tα−1(1 − t)β−1dt3170904.2 探索与利用：Beta分布04.3 Thompson Sampling0为了简化讨论，我们首先提供Bernoulli问题的ThompsonSampling算法的详细信息，即当奖励为0或1时，对于网关i，成功的概率（奖励=1）为  µ i。接下来，我们提出了这个算法的一个简单的新扩展，适用于支持[0,1]的一般奖励分布。0Bernoulli网关的算法在Bernoulli均值  µ ′ i上维护贝叶斯先验。贝塔分布是Bernoulli奖励的一个非常方便的选择。让我们简要回顾一下贝塔分布是连续概率分布的一族，定义在区间(0, 1)上。标准贝塔分布给出了区间(0,1)上值 x 的概率密度：0图3：随着 β增加的贝塔分布。注意图形在健康值较低处变得更加尖锐。0图4：随着 α增加的贝塔分布。注意图形在健康值较高处变得更加尖锐。0贝塔分布是Bernoulli奖励的一个非常方便的先验选择。让我们简要回顾一下贝塔分布是连续概率分布的一族，定义在区间(0,1)上。标准贝塔分布给出了区间(0,1)上值 x 的概率密度：0其中 B 是贝塔函数0。Beta( α ,  β ) 的均值是  α /( α  +  β)；从概率密度函数可以看出，  α ,  β 越大，Beta( α ,  β )的集中度越高。贝塔分布对于Bernoulli奖励很有用，因为如果先验是贝塔( α ,  β)分布，那么观察到Bernoulli试验后，后验分布就是简单的Beta( α+1,  β )或Beta( α , β+1)，具体取决于试验结果是成功还是失败。ThompsonSampling算法最初假设网关 i 具有先验Beta(1, 1)的  µ i，这是自然的，因为Beta(1, 1)是(0, 1)上的均匀分布。在时间t，观察到网关 i 的 k i ( t )  =  α t  +  β t  个交易中有  α t个成功（奖励=1）和  β t  个失败（奖励=0），算法进行更新：0Track: 社交感知与企业智能 朝着智能企业转型 WWW 2018年4月23日-27日，法国里昂αt+1 = λ(αt + rt )(5)βt+1 = λ βt + rt(6)417100图5：随着 α增加的贝塔分布。注意图形在健康值较高处变得更加尖锐。0表1：Thompson算法0Thompson Sampling算法 1:  α i  = 0,  β i  = 0. 2: 对于 t =1, 2, . . . ，执行以下操作 3: 对于每个网关 i = 1, . . . ,N，从参数为 (  α i  +1,  β i  + 1) 的贝塔分布中采样  θ i ( t )。 4: 推荐交易 i ( t )  := arg  max i θ i ( t ) 并观察奖励  r 。5: 如果 r = 1，则  α i  =  α i  + 1，否则  β i =  β i  + 1。 6:结束循环0将  µ i 的分布视为 Beta( α t  + 1,  β t  + 1)。然后算法从这些  µ ′ i的后验分布中进行采样，并根据其均值为最大的概率通过网关处理交易。我们在下面总结了 Thompson Sampling 算法（表1）。04.4 非稳定奖励0更新 α t 和 β t可以适用于稳定环境，其中奖励的概率分布是稳定的，但是网关的成功率随时间变化，网关的健康状况不断变化，因此分布实际上是非稳定的。在这种情况下，将最近的奖励与过去的奖励相比更重要是有意义的。我们使用了一个恒定的步长参数来实现这一点，并称之为历史衰减因子。因此，α t 和 β t 的更新方式如下：0请注意，λ是衰减因子，r t是时期t的奖励。衰减历史还有助于设置α t 和 β t 的值的上限。这些值的上限0表2：汤普森采样算法0带衰减的汤普森采样算法 1: α i = 0，β i = 0。 2: 对于 t =1, 2, . . . ，执行以下操作 3: 对于每个网关 i = 1, . . . ,N，从参数为 (α i +1, β i + 1) 的beta分布中采样 θ i ( t )。4: 为交易 i ( t ) 推荐 := arg max i θ i ( t ) 并观察奖励 { r α t, r β t }。 5: α i = λ ( α i + r α t )，β i = λ ( β i + r β t )。6: 结束循环0确保探索的可能性。我们考虑将奖励简化为只有0和1，以便讨论的简单性，但这些奖励可以是0和1之间的任何值，以表示各种奖励。例如，在我们的情况下，由于风险规则导致的交易失败并不意味着网关健康状况下降，因此其奖励可以在0和1之间变化。具有更新的汤普森算法可以总结如下（表2）：05 结果和讨论0我们在图6中比较了推荐的和现有的动态切换算法的成功率。当前的实现会查看每个网关的月度、每周和每小时成功率，以便为交易提供建议。使用贝叶斯定理计算了成功交易的概率。该实现采用了每个网关的离散成功率的概念。对于新的网关或被标记为故障的网关，定期进行探索。0•图6和图7表示整体交易流量和PayU前20个商家的成功率比较。•数据基于特定商家允许的网关。•CURRENT_SR：当前实现实现的成功率。根据当前设置，强制每个交易的合格支付网关。•RECOMMENDED_SR：新学习算法的成功率。•BEST_SR：如果为商家启用了所有合格的网关，则可能的最佳成功率。•合格网关：每个交易都有一组可以处理该交易的合格网关。该集合取决于客户使用的支付方式和商家启用的网关。05.1 影响0•提出的实现使整体成功率提高了3.23％，而不会改变网关对于根据商家和bin的交易的合格性的任何安排。•如果为所有可路由的网关启用，则提出的实现使整体成功率提高了8.21％。这仅考虑了给定交易的合格网关，以及交易的bin处理能力。•提出的实现提供了预测特定支付网关的成功率和成本的能力。0论文题目：社交感知与企业智能 朝着智能企业转型 WWW 2018，2018年4月23日至27日，法国里昂Figure 6: Recommended vs Current Success Rates.enabled for all the transactions. This considers only eligiblegateways for a given transaction in terms of bin processingability of a transaction.• The proposed implementation provides an ability to predictthe success rate and the cost if a particular payment gateway517110图7：推荐的成功率与当前成功率与最佳成功率的比较。0对于商家而言，启用了一个特定的支付网关。这可以用来让商家了解启用特定网关的可见性。这也有助于在商家上启用更多的网关，并在交易路由时获得更多选择的好处。•提出的解决方案使我们能够预测各种排列中各个网关之间的交易量转移。•通过较小金额的交易进行探索，从而减少由于探索过程而产生的损失。•提出的实现对网关健康状况的变化更加敏感，因此在网关故障或恢复健康时表现更好。•基于成本的路由改进了整体利润率，而不会影响成功率。06 结论0将强化学习应用于交易路由问题在成功率和利润率方面取得了显著的改进。奖励调整也进一步提高了我们对各种故障原因对整体成功率的影响的理解。对机器学习和尤其是强化学习的兴趣日益增长，这源于大量可建模为多路径路由问题的工业相关问题。从机器人技术到游戏玩法、辅导系统、资源管理、金融投资组合管理、医疗治疗设计等，许多科学和工程领域的问题都可以被描述为在不确定性下的顺序决策问题。本文介绍的技术可以通过简单修改用于奖励分配的模型来推广到许多类似的问题。0跟踪: 社交感知和企业智能  迈向智能企业转型 WWW 2018, 2018年4月23-27日, 法国里昂617120参考文献0[1]  Omar Besbes, Yonatan Gur, Assaf Zeevi非稳态奖励的多臂赌博问题的最优探索-开发. [2]  P. Auer, N. Cesa-Bianchi, 和 P. Fischer.多臂赌博问题的有限时间分析.  《机器学习》, 47(2-3):235-256, 2002. [3]  M. Zelen.胜者为王规则和受控临床试验.  《美国统计协会杂志》, 64:131-146, 1969. [4]  D. A. Berry和 B. Fristedt.  赌徒问题: 顺序分配实验. Chapman and Hall, 1985. [5]  O. Chapelle 和 L.Li.  汤普森抽样的实证评估.  在NIPS, 2011. [6]  P. Auer, N. Cesa-Bianchi, 和 P. Fischer.多臂赌博问题的有限时间分析.  《机器学习》, 2002. [7]  R. D. Kleinberg 和 T. Leighton.知道需求曲线的价值: 在线定价拍卖的遗憾上界.在第44届IEEE计算机科学基础研讨会(FOCS)论文集上, 页码594-605, 2003. [8]  SebastienBubeck 和 Nicolo Cesa-Bianchi.  随机和非随机多臂赌博问题的遗憾分析.《机器学习基础与趋势》, 5(1):1-122, 2012. [9]  J. C. Gittins.赌徒过程和动态分配指数(含讨论).  《皇家统计学会B系列杂志》, 41:148-177, 1979. [10]O. Besbes, Y. Gur, 和 A. Zeevi.  非稳态随机优化.  工作论文, 2014. [11]  S. Agrawal 和 N.Goyal.  汤普森抽样在多臂赌博问题中的分析.  CoRR, abs/1111.1797, 2011.0[12]  M. Babaioff, Y. Sharma, and A. Slivkins.  揭示真实的多臂赌博机机制: 扩展摘要.在第十届ACM电子商务会议上, 页码79-88. ACM, 2009. [13]  O. Chapelle and L. Li.汤普森抽样的实证评估.  在J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, 和 K.Weinberger等编辑的《神经信息处理系统24》中, 页码2249-2257. Curran Associates,Inc., 2011. [14]  N. Gatti, A. Lazaric, 和 F. TrovÚ.一种用于带外部性的上下文多槽赞助搜索拍卖的真实学习机制.在第十三届ACM电子商务会议上, 页码605-622, 2012. [15]  O.-C. Granmo.使用贝叶斯学习自动机解决两臂伯努利赌博问题.  《智能计算与控制国际期刊》,3(2):207-234, 2010. [16]  S. Scott.  多臂赌博机的现代贝叶斯观点.《应用随机模型在商业和工业中的应用》, 26:639-658, 2010. [17]  D. Bergemann and J.Valimaki.  学习和策略定价.  《计量经济学》, 64:1125-1149, 1996. [18]  D. Bergemannand U. Hege.  创新的融资: 学习和停止.  《兰德经济学杂志》, 36 (4):719-752, 2005. [19]B. Awerbuch and R. D. Kleinberg.  具有端到端反馈的自适应路由: 分布式学习和几何方法.在第36届ACM计算理论研讨会(STOC)论文集上, 页码45-53, 2004. [20]  F. Caro and G.Gallien.  季节性消费品的动态组合与需求学习.  《管理科学》, 53:276-292, 2007. [21]  S.Pandey, D. Agarwal, D. Charkrabarti, 和 V. Josifovski.  用于分类法的赌徒算法:一种基于模型的方法.  在SIAM国际数据挖掘会议上, 2007.0跟踪：社交感知和企业智能 朝着智能企业转型 WWW 2018年4月23日至27日，法国里昂