考虑时变奖励的多摇臂算法在动态定价中的应用

考虑到动态定价是一个非固定性的多摇臂（Multi-Armed Bandit,MAB）问题,即厂商的利润会随时间变化,因此在相关研究基础上,研究了需求不确定情况下考虑时变奖励的置信区间上界（Upper Confidence Bound,UCB）算法在动态定价问题上的应用。将商品定价问题描述为一个多摇臂问题,并构建利润最大化模型求得最优解。仿真结果表明,通过将考虑时变奖励的置信区间上界算法与基础的多摇臂算法进行对比分析,所提出的算法学得的奖励更加接近真实奖励,收敛速度更快。相较于前人研究,该模型考虑了时变因素,更加符合现实场景中的动态定价,为厂商定价提供了相应的决策支持。     

一种满足差分隐私的图赌博机算法

图赌博机是一种重要的不确定性环境下的序列决策模型, 在社交网络、电子商务和推荐系统等领域都得到了广泛的应用. 目前, 针对图赌博机的工作都只关注如何快速识别最优摇臂从而最小化累积遗憾, 而忽略了在很多应用场景中存在的隐私保护问题. 为了克服现有图赌博机算法的缺陷, 提出了一种满足差分隐私的图赌博机算法GAP (图反馈下的差分隐私摇臂消除策略). 一方面, GAP算法阶段性地根据摇臂的经验平均奖赏更新摇臂选取策略, 并在计算摇臂的经验平均奖赏时引入拉普拉斯噪声, 从而确保恶意攻击者难以根据算法输出推算摇臂奖赏数据, 保护了隐私. 另一方面, GAP算法在每个阶段根据精心构造的反馈图的独立集探索摇臂集合, 有效地利用了图形式的反馈信息. 证明了GAP算法满足差分隐私性质, 具有与理论下界相匹配的遗憾界. 在仿真数据集上的实验结果表明: GAP算法在有效保护隐私的同时取得了与现有无隐私保护的图赌博机算法相当的累积遗憾.     

考虑参照价格效应的易逝品定价与订购策略

在考虑消费者参照价格效应的基础上,构建一个易逝品的定价与订购联合决策模型,其中产品的需求不仅依赖于销售价格还与该产品在消费者心目中的参照价格相关,变质率为常数,系统不允许缺货.分别讨论了对称参照价格效应和非对称参照价格效应两种情况下零售商的最优定价与订购决策问题,证明并得到关于模型结构的一些性质,进而设计了问题的求解算法.通过数值方法分析了参照价格效应参数和变质率对系统最优解的影响,以及两种情况下最优解之间的关系.结果显示:当面对具有参照价格依赖的消费者时,采用适当的营销策略来提高消费者的参照价格对零售商总是有利的;对高变质率产品而言,零售商可保持一个较稳定的订购策略,更多地关注产品的定价策略;面对损失厌恶型消费者,随着消费者参照价格的逐渐提高,零售商的定价与订购策略均应缓慢地改变,而不宜急剧变化.     

基于最小购买模式的多产品定价方法

通过与顾客的在线交互,电子商务网站能够获得消费者反馈的有关参考数据。这些有效的数据结合完善的分析工具可使企业通过价格的优化来增加效益。基于这些有效数据研究了多产品定价问题,其中,给定消费者有关产品的参考数据(包括预算和定购产品列表),通过设定一个企业多个产品的价格,极大化企业的总收益;提出了基于最小购买模式的多产品定价问题模型,设计了针对该模型的遗传算法。仿真实例证明了该模型的有效性。     

网上零售业多产品配送服务定价研究

随着越来越多的网上零售商开始实施有条件的免运费策略,如何确定免运费的条件和运费成为电商企业面临的重要问题。该问题抽象成为一个两阶段的博弈模型:首先消费者根据效用最大化的原则确定购买决策,然后零售商在考虑消费者购买决策的基础上依据利润最大化原则设定物流定价策略。通过算法设计和算例分析,得到免运费阈值设定在产品价格组合边界时,零售商利润会发生跳跃。     

网上零售业多产品配送服务定价研究

随着越来越多的网上零售商开始实施有条件的免运费策略, 如何确定免运费的条件和运费成为电商企业面临的重要问题。该问题抽象成为一个两阶段的博弈模型：首先消费者根据效用最大化的原则确定购买决策, 然后零售商在考虑消费者购买决策的基础上依据利润最大化原则设定物流定价策略。通过算法设计和算例分析, 得到免运费阈值设定在产品价格组合边界时, 零售商利润会发生跳跃。     

稳健的重尾线性赌博机算法

线性赌博机模型是在线学习的基本模型之一，其每个摇臂的平均奖赏可以由线性函数进行参数化.该模型具有坚实的理论保证和良好的实际建模能力，被广泛应用于各个场景.然而在一些现实场景中，数据通常是从开放动态环境中收集得到，因而会存在数据不规范的问题，已有算法缺乏对此的稳健性.特别关注2类数据的不规范性：奖励函数的回归参数可能随时间变化，环境噪声可能无界，甚至不服从亚高斯分布.这2类问题分别被称为分布变化和重尾噪声.为了应对这2类不利因素，提出一种基于置信上界的在线算法，该算法使用均值中位数估计器以处理潜在的重尾噪声，同时采用重启机制来解决分布变化问题.在理论上，首先建立了问题的遗憾理论下界，进一步给出了算法的理论保障，所取得的结果可以回退到已有研究中没有分布变化或没有重尾噪声场景线性赌博机的理论结果.此外，针对未知环境设计了实用的在线集成适应技术，并在合成和真实世界的数据集上进行了广泛的实验来验证其有效性.     

在线核选择的对抗式多臂赌博机模型

在线核选择是在线核方法的重要工作,可分为过滤式、包裹式和嵌入式3种类型。已有在线核选择探索了包裹式方法和嵌入式方法,也经验地采用了过滤式方法,但迄今尚没有一个统一的框架来比较、分析并研究各种在线核选择问题。文中 提出一种在线核选择的多臂赌博机模型,该模型可作为一个统一框架,同时给出在线核选择的包裹式方法和嵌入式方法。给定候选核集合,候选集中的一个核对应多臂赌博机模型中的一个臂,在线核选择的每回合依据一个概率分布重复地随机选择多个核,并应用指数加权的方法来更新该概率分布。这样,在线核选择问题本质上可归约为一个非遗忘对手环境下的对抗式多臂赌博机问题,并可应用对抗式多臂赌博机模型统一地给出在线核选择的包裹式方法和嵌入式方法。文中进一步提出一个新的在线核选择后悔的概念,理论证明包裹式方法具有关于回合数亚线性的弱期望后悔界,并且嵌入式方法具有关于回合数亚线性的期望后悔界。最后,在标准数据集上通过实验验证了所提统一框架的可行性。     

基于报童模型和贪心算法的订货管理系统

市场需求的不确定会对零售商订货决策造成困难。为解决该问题,将多产品报童模型与贪心算法相结合,基于主流开发技术,设计一个功能齐全、操作简便的零售商订货管理系统,为零售商在需求不确定情况下的订货决策提供支持。仿真实验结果表明,与依靠经验决策获得的订货方案相比,利用该系统求得的订货方案具有明显优势。     

消费者等待和转移购买行为下的易逝品定价策略

针对消费者等待和转移两种购买行为下的易逝品销售市场,构建两阶段双寡头零售商降价和匹配定价模型,讨论模型的简化运算方式,分析两种行为构成比例对零售商决策的影响,并进一步论证降价和匹配定价策略的有效性.研究表明,消费者异质购买行为下,等待和转移消费者的构成比例是零售商决策的重要因素,对零售商的期望收益具有双向影响;当消费者延迟购买程度适中时,低需求零售商应主动采取价格匹配策略,并辅以更大程度地降价形成与高需求零售商"不直接对话"的协调,实现市场帕累托改进,否则降价策略是其唯一的可选策略.高需求零售商也可主动采取两周期价格匹配策略,在消费者延迟购买意愿强烈的情况下缓解与低需求零售商的竞争,实现期望收益增加.     

Adaptive crawler for external hyperlinks search and acquisition

We describe a search robot (crawler) intended to collect information regarding outgoing hyperlinks from a given set of web sites related to a certain topic. The crawler’s adaptive behavior is formulated in terms of a multi-armed bandit problem. Our experiments show that the choice of an adaptive algorithm for the crawler’s rational behavior depends on the actual topic of the underlying set of web sites.     

考虑参考效应的网络零售商配送时隙定价研究

由于电商的快速发展，客户在购买商品时可根据内外部因素了解商品的历史信息，依据历史信息和现在商品信息做出比较，这些行为会对需求有一定影响，形成参考效应。在参考效应的影响下，探讨在含有参考价格的参考效应下对网络零售商配送时隙定价以及收益的影响，在效用函数中加入参考价格因素，建立logit选择模型，提出具有参考效应的收益模型。结果表明：参考效应强度的不同对时隙选择的影响不同，参考价格的增加，会造成网络零售商的收益增加。参考效应影响下，网络零售商的配送时隙收益随时隙定价的增加先增后减，研究结果对零售商配送时隙定价具有参考意义。     

Online linear optimization and adaptive routing

This paper studies an online linear optimization problem generalizing the multi-armed bandit problem. Motivated primarily by the task of designing adaptive routing algorithms for overlay networks, we present two randomized online algorithms for selecting a sequence of routing paths in a network with unknown edge delays varying adversarially over time. In contrast with earlier work on this problem, we assume that the only feedback after choosing such a path is the total end-to-end delay of the selected path. We present two algorithms whose regret is sublinear in the number of trials and polynomial in the size of the network. The first of these algorithms generalizes to solve any online linear optimization problem, given an oracle for optimizing linear functions over the set of strategies; our work may thus be interpreted as a general-purpose reduction from offline to online linear optimization. A key element of this algorithm is the notion of a barycentric spanner, a special type of basis for the vector space of strategies which allows any feasible strategy to be expressed as a linear combination of basis vectors using bounded coefficients.We also present a second algorithm for the online shortest path problem, which solves the problem using a chain of online decision oracles, one at each node of the graph. This has several advantages over the online linear optimization approach. First, it is effective against an adaptive adversary, whereas our linear optimization algorithm assumes an oblivious adversary. Second, even in the case of an oblivious adversary, the second algorithm performs slightly better than the first, as measured by their additive regret.     

Pricing strategies in online book industry: a comparative study

In this paper, we examine pricing strategies in the U.S. online book industry over two time periods, with an aim to understand whether and how the driving factors of price dispersion change over time. Our empirical results show that dispersion in prices has remained substantial over the period of 2001–2006, but the driving factors of these variations in price have evolved. In 2001 online book retailers generally engaged in obfuscation, frustrating consumer search by manipulating shipping options. As documented by prior literature and revealed in our 2001 data, higher prices charged by retailers were positively related with longer shipping time. This strategy has been abandoned, as shown by our results of a 2006 sample. Online retailers are now competing to ship items quicker than rivals and to pass fewer or no shipping costs on to consumers. The impact of trust assurance seals (e.g., seals of online security and privacy) on price has materialized over the period of 2001–2006. This is because as more consumers become security conscious, the effects of assurance seals on the price becomes better recognized. Moreover, although retailers are roughly clustered into three cohorts, they strategize prices across different product items within each cohort.     

Competitive collaborative learning

Intuitively, it is clear that trust or shared taste enables a community of users to make better decisions over time, by learning cooperatively and avoiding one another's mistakes. However, it is also clear that the presence of malicious, dishonest users in the community threatens the usefulness of such collaborative learning processes. We investigate this issue by developing algorithms for a multi-user online learning problem in which each user makes a sequence of decisions about selecting products or resources. Our model, which generalizes the adversarial multi-armed bandit problem, is characterized by two key features:

(1)

The quality of the products or resources may vary over time.

(2)

Some of the users in the system may be dishonest, Byzantine agents.

Decision problems with these features underlie applications such as reputation and recommendation systems in e-commerce, and resource location systems in peer-to-peer networks. Assuming the number of honest users is at least a constant fraction of the number of resources, and that the honest users can be partitioned into groups such that individuals in a group make identical assessments of resources, we present an algorithm whose expected regret per user is linear in the number of groups and only logarithmic in the number of resources. This bound compares favorably with the naïve approach in which each user ignores feedback from peers and chooses resources using a multi-armed bandit algorithm; in this case the expected regret per user would be polynomial in the number of resources.     

在线影响力最大化研究综述

影响力最大化是指在给定的影响力传播模型下选取种子节点使其传播信息范围最广。此问题的应用场景十分广泛,包括推荐系统、病毒营销、信息扩散和链接预测等。在实际应用中,信息传播模型中的点对点传播概率通常是未知的,而在线学习算法可以在交互过程中自主学习未知参数,逐步逼近最优解。文中首先讨论了影响力最大化问题的定义,介绍了常用的影响力传播模型,归纳了常见的离线影响力最大化算法;随后介绍了经典的在线学习框架——多臂老虎机问题,分析了在线影响力最大化问题的研究现状,并通过实验对常见的在线影响力最大化算法在真实社交网络中的性能表现进行对比;最后总结了该课题面临的挑战并展望了未来的研究方向。     

基于多臂赌博机的时变信道速率自适应选择方法

针对在复杂多变的无线通信环境中合适的传输速率难以确定,导致吞吐率下降的问题,提出了一种基于多臂赌博机模型的跨层速率自适应选择算法(DUCB-RA,Discounted Upper Confidence Bound Based Rate Adaptation),把速率选择问题转换为多臂赌博机(MAB,Multi-Armed Bandit)问题,同时利用了物理层以及媒体接入控制层反馈的信道信息来选择合适的发送速率。在最后给出了算法性能的数学证明和仿真结果。实验结果表明,与其他速率自适应选择方案相比,该算法在平稳以及时变信道条件下均能取得较好的性能。     

Asymptotically optimal algorithms for budgeted multiple play bandits

Machine Learning - We study a generalization of the multi-armed bandit problem with multiple plays where there is a cost associated with pulling each arm and the agent has a budget at each time...     

Multi-objective multi-armed bandit with lexicographically ordered and satisficing objectives

Machine Learning - We consider multi-objective multi-armed bandit with (i) lexicographically ordered and (ii) satisficing objectives. In the first problem, the goal is to select arms that are...