Stochastic programming based multi-arm bandit offloading strategy for internet of things

In order to solve the high latency of traditional cloud computing and the processing capacity limitation of Internet of Things(IoT)users,Multi-access Edge Computing(MEC)migrates computing and storage capabilities from the remote data center to the edge of network,providing users with computation services quickly and directly.In this paper,we investigate the impact of the randomness caused by the movement of the IoT user on decision-making for offloading,where the connection between the IoT user and the MEC servers is uncertain.This uncertainty would be the main obstacle to assign the task accurately.Consequently,if the assigned task cannot match well with the real connection time,a migration(connection time is not enough to process)would be caused.In order to address the impact of this uncertainty,we formulate the offloading decision as an optimization problem considering the transmission,computation and migration.With the help of Stochastic Programming(SP),we use the posteriori recourse to compensate for inaccurate predictions.Meanwhile,in heterogeneous networks,considering multiple candidate MEC servers could be selected simultaneously due to overlapping,we also introduce the Multi-Arm Bandit(MAB)theory for MEC selection.The extensive simulations validate the improvement and effectiveness of the proposed SP-based Multi-arm bandit Method(SMM)for offloading in terms of reward,cost,energy consumption and delay.The results showthat SMMcan achieve about 20%improvement compared with the traditional offloading method that does not consider the randomness,and it also outperforms the existing SP/MAB based method for offloading.

Starlet:Network defense resource allocation with multi-armed bandits for cloud-edge crowd sensing in IoT

The cloud platform has limited defense resources to fully protect the edge servers used to process crowd sensing data in Internet of Things.To guarantee the network's overall security,we present a network defense resource allocation with multi-armed bandits to maximize the network's overall benefit.Firstly,we propose the method for dynamic setting of node defense resource thresholds to obtain the defender(attacker)benefit function of edge servers(nodes)and distribution.Secondly,we design a defense resource sharing mechanism for neighboring nodes to obtain the defense capability of nodes.Subsequently,we use the decomposability and Lipschitz conti-nuity of the defender's total expected utility to reduce the difference between the utility's discrete and continuous arms and analyze the difference theoretically.Finally,experimental results show that the method maximizes the defender's total expected utility and reduces the difference between the discrete and continuous arms of the utility.

融合协同过滤的神经Bandits推荐算法

针对数据稀疏性和“冷启动”对协同过滤的限制以及现有的协同多臂老虎机算法不适用于非线性奖励函数的问题,提出一种融合协同过滤的神经Ba ndits推荐算法COEENet.首先,采用双神经网络结构学习预期奖励及潜在增益;其次,考虑邻居协同作用;最后,构造决策器进行最终决策.实验结果表明,该方法在累积遗憾上优于4种基线算法,推荐效果较好.

Distributed Weighted Data Aggregation Algorithm in End-to-Edge Communication Networks Based on Multi-armed Bandit

As a combination of edge computing and artificial intelligence,edge intelligence has become a promising technique and provided its users with a series of fast,precise,and customized services.In edge intelligence,when learning agents are deployed on the edge side,the data aggregation from the end side to the designated edge devices is an important research topic.Considering the various importance of end devices,this paper studies the weighted data aggregation problem in a single hop end-to-edge communication network.Firstly,to make sure all the end devices with various weights are fairly treated in data aggregation,a distributed end-to-edge cooperative scheme is proposed.Then,to handle the massive contention on the wireless channel caused by end devices,a multi-armed bandit(MAB)algorithm is designed to help the end devices find their most appropriate update rates.Diffe-rent from the traditional data aggregation works,combining the MAB enables our algorithm a higher efficiency in data aggregation.With a theoretical analysis,we show that the efficiency of our algorithm is asymptotically optimal.Comparative experiments with previous works are also conducted to show the strength of our algorithm.

Millimeter-Wave Concurrent Beamforming:A Multi-Player Multi-Armed Bandit Approach

The communication in the Millimeter-wave(mmWave)band,i.e.,30~300 GHz,is characterized by short-range transmissions and the use of antenna beamforming(BF).Thus,multiple mmWave access points(APs)should be installed to fully cover a target environment with gigabits per second(Gbps)connectivity.However,inter-beam interference prevents maximizing the sum rates of the established concurrent links.In this paper,a reinforcement learning(RL)approach is proposed for enabling mmWave concurrent transmissions by finding out beam directions that maximize the long-term average sum rates of the concurrent links.Specifically,the problem is formulated as a multiplayer multiarmed bandit(MAB),where mmWave APs act as the players aiming to maximize their achievable rewards,i.e.,data rates,and the arms to play are the available beam directions.In this setup,a selfish concurrent multiplayer MAB strategy is advocated.Four different MAB algorithms,namely,ϵ-greedy,upper confidence bound(UCB),Thompson sampling(TS),and exponential weight algorithm for exploration and exploitation(EXP3)are examined by employing them in each AP to selfishly enhance its beam selection based only on its previous observations.After a few rounds of interactions,mmWave APs learn how to select concurrent beams that enhance the overall system performance.The proposed MAB based mmWave concurrent BF shows comparable performance to the optimal solution.

Strict greedy design paradigm applied to the stochastic multi-armed bandit problem

The process of making decisions is something humans do inherently and routinely,to the extent that it appears commonplace. However,in order to achieve good overall performance,decisions must take into account both the outcomes of past decisions and opportunities of future ones. Reinforcement learning,which is fundamental to sequential decision-making,consists of the following components: 1 A set of decisions epochs; 2 A set of environment states; 3 A set of available actions to transition states; 4 State-action dependent immediate rewards for each action.At each decision,the environment state provides the decision maker with a set of available actions from which to choose. As a result of selecting a particular action in the state,the environment generates an immediate reward for the decision maker and shifts to a different state and decision. The ultimate goal for the decision maker is to maximize the total reward after a sequence of time steps.This paper will focus on an archetypal example of reinforcement learning,the stochastic multi-armed bandit problem. After introducing the dilemma,I will briefly cover the most common methods used to solve it,namely the UCB and εn- greedy algorithms. I will also introduce my own greedy implementation,the strict-greedy algorithm,which more tightly follows the greedy pattern in algorithm design,and show that it runs comparably to the two accepted algorithms.

Training a Quantum Neural Network to Solve the Contextual Multi-Armed Bandit Problem

Artificial intelligence has permeated all aspects of our lives today. However, to make AI behave like real AI, the critical bottleneck lies in the speed of computing. Quantum computers employ the peculiar and unique properties of quantum states such as superposition, entanglement, and interference to process information in ways that classical computers cannot. As a new paradigm of computation, quantum computers are capable of performing tasks intractable for classical processors, thus providing a quantum leap in AI research and making the development of real AI a possibility. In this regard, quantum machine learning not only enhances the classical machine learning approach but more importantly it provides an avenue to explore new machine learning models that have no classical counterparts. The qubit-based quantum computers cannot naturally represent the continuous variables commonly used in machine learning, since the measurement outputs of qubit-based circuits are generally discrete. Therefore, a continuous-variable (CV) quantum architecture based on a photonic quantum computing model is selected for our study. In this work, we employ machine learning and optimization to create photonic quantum circuits that can solve the contextual multi-armed bandit problem, a problem in the domain of reinforcement learning, which demonstrates that quantum reinforcement learning algorithms can be learned by a quantum device.

基于Bandit反馈的自适应量化分布式在线镜像下降算法

多智能体系统的在线分布式优化常用于处理动态环境下的优化问题,节点间需要实时传输数据流.在很多情况下,各节点无法获取个体目标函数的全部信息(包括梯度信息),并且节点间信息传输存在一定的通信约束.考虑到非欧投影意义下的镜像下降算法在处理高维数据和大规模在线学习上的优势,本文使用个体目标函数在两点处的函数值信息对缺失的梯度信息进行估计,并且根据镜像下降算法的性质设计自适应量化器,提出基于Bandit反馈的自适应量化分布式在线镜像下降算法.然后分析了量化误差界和Regret界的关系,适当选择参数可得所提算法的Regret界为O(√T).最后,通过数值仿真验证了算法和理论结果的有效性.

基于强化学习的大规模多模Mesh网络联合路由选择及资源调度算法

为了平衡新型电力系统中大规模多模Mesh网络的传输可靠性和效率,该文在对优化问题进行描述和分析的基础上提出一种基于强化学习的大规模多模Mesh网络联合路由选择及资源调度算法,分为两个阶段。在第1阶段中,根据网络拓扑结构信息和业务需求,利用一种多条最短路径路由算法,输出所有最短路径。在第2阶段中,提出一种基于多臂老虎机(MAB)的资源调度算法,该算法基于得到的最短路径集合构建MAB的摇臂,然后根据业务需求计算回报,最终给出最优的路由选择及资源调度方式用于业务传输。仿真结果表明,所提算法能够满足不同的业务传输需求,实现端到端路径的平均时延和平均传输成功率的高效平衡。

面向不平衡类的联邦学习客户端智能选择算法

在联邦学习应用场景下,若客户端设备之间的数据呈现非独立同分布特征,甚至出现类不平衡的情况时,客户端本地模型的优化目标将偏离全局优化目标,从而给全局模型的性能带来巨大挑战。为解决这种数据异质性带来的挑战,通过积极选择合适的客户端子集以平衡数据分布将有助于提高模型的性能。因此,设计了一种面向不平衡类的联邦学习客户端智能选择算法—FedSIMT。该算法不借助任何辅助数据集,在保证客户端本地数据对服务器端不可见的隐私前提下,使用Tanimoto系数度量本地数据分布与目标分布之间的差异,采用强化学习领域中的组合多臂老虎机模型平衡客户端设备选择的开发和探索,在不同数据异质性类型下提高了全局模型的准确率和收敛速度。实验结果表明,该算法具有有效性。

基于选择的移动群智感知反向拍卖激励机制

由于移动群智感知中工人和平台的自私性,社会福利和数据质量往往难以达到平衡,损害了基于移动群智感知的服务可用性和准确性。为了解决这一问题,本文提出一种基于选择的反向拍卖激励机制,分别研究反向拍卖中以工人为中心的任务选择和以平台为中心的工人选择,在最大限度提高社会福利的同时优化数据质量。首先,根据工人和任务的位置等属性评估工人与任务之间的匹配度,提出基于动态规划的任务选择算法,在工人资源约束下为每个工人选择具有最佳回报的任务进行投标;其次,使用多臂赌博机建模反向拍卖赢家选择过程,并设计了一种基于置信度上界的赢家选择算法,以确定最佳中标工人集;最后,实验验证本文所提出的激励机制能够同时有效提升社会福利和数据质量。

基于AntConc的《水浒传》中梁山形象的嬗变

以往对《水浒传》中形象的研究大多关涉人物,鲜少涉及梁山形象。本文基于AntConc自建数据库,比较并分析原文本和沙博理译本中的梁山形象,考察作者和译者对梁山形象认知的异同。研究发现:梁山形象经过了三个典型阶段的嬗变,从自然地理形象到绿林强盗形象,再到忠义英雄形象。梁山形象的演进与梁山故事的推进呈现出一致性的特点。译本中有关梁山形象的表述体现了译者主体性。

对新产品开发的最优价值分析——基于Bandit过程的模型研究

新产品开发的成败直接关系到企业的生存和发展,因而有效的新产品开发始终是企业追求的目标。本文运用备择Bandit过程的原理对新产品开发的最优价值进行了一定程度的探讨。本文的最后结论认为新产品开发的最优价值取决于Gittins指标法则的有效性,即最终取决于市场占有率,对新产品需求预测的准确性,对消费者认知价值预测的准确性以及新产品投放市场的有效性,对这些变量的预测越精确,最优规则越有效,新产品开发成功的价值越大。

基于上下文多摇臂赌博机的交通信号控制算法

近年来,由于交通拥堵问题日益严重,引起了学术界对交通信号灯控制算法研究的广泛关注.现有研究表明,基于深度强化学习(DRL)的方法在模拟环境中表现良好,但在实际应用中存在着数据和计算资源需求大、难以实现路口之间协同等问题.为解决这一问题,本文提出了一种基于上下文多摇臂赌博机的新型交通信号控制算法.与传统方法相比,本文所提算法通过从路网中提取主干道的方式,实现了路口之间的高效协同,并利用上下文多摇臂赌博机模型实现了交通信号的快速、有效控制.最后,通过在真实数据集以及合成数据集上进行充分的实验验证,证明了本文算法相较于过去算法的优越性.

单臂Erlang(k) Bandit报酬过程

应用贝叶斯方法,对未知Band it报酬过程的抽样报酬基于Erlang(k)分布的单臂Erlang(k)Band it报酬过程提出计算描述最优选择的平衡值序列的算法.有效解决了单臂Erlang(k)Band it报酬过程的最优决策问题,将Band it报酬过程基于的分布从负指数分布推广至目前在实际中应用更为广泛的分布,是对Band it报酬过程的补充和推广.使用本算法通过数值计算可以得到G ittins指数的近似解.

面向异构ICN节点的副本选择算法研究

信息中心网络(ICN)是一种革新式网络架构,打破了传统TCP/IP网络端到端传输的限制,提升内容分发效率。ICN构建全网规模的缓存系统,在网络内采用多副本冗余的方式缓存数据内容,以便用户就近获取。与传统互联网缓存系统不同,ICN的缓存呈现泛在化的特点,工作设备是网络基础设施,导致服务资源的异构性普遍存在。在这种环境下,选择适当的副本节点成为重要研究问题。本文首先通过M/M/1排队模型对异构ICN节点进行抽象建模和分析,然后将异构副本节点的选择建模成多臂老虎机问题,继而引入UCB1算法来探索并学习最优决策。仿真实验结果表明,该算法在提高缓存服务可靠性和缩短内容获取时延方面具有明显优势,算法使服务可靠性达到99.15%,将内容获取的平均时延最大缩短8.63%。

MOOB:一种改进的基于Bandit模型的推荐算法

提出了一种基于置信区间上界算法的多目标优化推荐算法.该算法可以在保证预测精准度的基础上有效地避免马太效应,并提高推荐系统对长尾物品的挖掘能力.采用Ya Hoo的新闻推荐数据集对算法进行了实验和评价,实验结果表明:多目标优化推荐算法能够在预测准确率较高的情况下,有效地解决长尾物品发掘问题,避免马太效应,提高推荐系统的精度和广度.

基于Fed-DPDOBO的分散式联邦学习

传统的客户-服务器架构联邦学习作为解决数据孤岛问题的有效手段,其中心服务器面临着巨大的带宽压力,分散式的对等架构联邦学习在一定程度上可改善这种情况。然而,联邦学习的客户端还存在着数据隐私泄露的风险,而且其成本函数梯度信息在某些情况下很难获得。针对这些问题,本文为一致性约束下的对等架构联邦学习设计一种Federated Differential Privacy Distributed One-point Bandit Online(Fed-DPDOBO)算法,可有效地解决中心服务器带宽限制和客户端梯度信息未知的问题。此外,差分隐私技术的运用,可很好地保护各客户端数据隐私。最后,通过利用MINST数据集进行分散式联邦学习实验,验证本文算法的有效性。

电力物联网中基于聚类的任务卸载在线优化方法

随着电力物联网(electric Internet of Things,eIoT)技术的快速发展,海量电力设备在网络边缘环境中产生了丰富的数据。移动边缘计算(Mobile Edge Computing,MEC)技术在靠近终端设备的位置部署边缘代理可以有效减少数据处理延迟,这使其非常适用于延迟敏感的电力物联网场景。然而,目前的大多数研究没有考虑到部分边缘终端设备也可以作为代理设备提供计算服务,造成了资源浪费。为了充分利用移动边缘计算过程中边缘代理以及边缘终端设备的计算能力,提出了一种基于设备聚类的任务卸载方案。首先,基于分层DBSCAN(hierarchical density-based spatial clustering of applications with noise)算法,对系统中的静态和动态边缘设备进行聚类。其次,将任务卸载问题建模为多臂老虎机(Multi-Armed Bandits,MAB)模型,目标为最小化卸载延迟。再次,提出了一种基于自适应置信上限算法的算法来寻找簇内与簇间的卸载策略。最后,仿真结果表明,该方案在平均延迟方面表现出了更好的性能,并且设备簇的存活时间延长了10%~20%。

强化学习中动态ε的贪婪探索策略

随着强化学习领域的成熟,ε-贪婪方法被广泛运用在强化学习中,例如深度Q网络。但是,对于ε-贪婪方法每次选择动作,它有一定概率选择非最优的动作,导致不断探索。在此背景下,提出了一种动态ε-贪婪方法(DEG)和Dueling Actor-Critic框架(ACDD),能够平衡强化学习中的探索和利用问题。DEG将状态输入到ACDD框架得到优势值来自动调整ε的值,从而保持探索和利用之间的更好平衡。该实验在多臂老虎机任务中对DEG进行测试,将累计平均奖励和最优动作选择率作为评估标准。与一些广泛使用的方法相比,DEG可以达到更高的平均累积奖励和最优动作选择率,并提高了性能。