Stochastic Adaptive Dynamics of a Simple Market as a Non-Stationary Multi-Armed Bandit Problem

Yann BRAOUEZEC

摘要

我们开发了一个动态垄断定价模型作为一个非平稳的多臂老虎机问题。 每次，垄断者在有限集合中选择一个价格，每个顾客随机但独立地决定是否访问他的商店。 每个客户都有两个参数，支付能力和访问概率。 我们的问题对于垄断者来说是非平稳的，因为每个客户都会根据经验修改他的概率。 我们为我们的问题定义了一个事前最优价格，然后看两种不同的方法来学习这个最优价格。 在第一部分中，假设垄断者除了支付能力之外什么都知道，我们建议一个基于购买行为的简单计数规则，它允许他获得足够的信息来计算最优价格。 在第二部分，假设没有特定知识，我们考虑垄断者使用自适应随机算法的情况。
当学习很容易（困难）时，我们的模拟表明垄断者（不）在每个样本路径上选择最优价格。
多臂老虎机问题，自适应学习，随机市场动态，探索-利用权衡，非平稳性

1 引言

经济理论家将市场均衡问题作为一个数学问题来研究：解的存在性、唯一性和稳定性。 稳定性产生了所谓的 tatonnement 模型，其中价格的自适应动态应该反映 walrasian 拍卖师的学习过程。 正如 Kirman 等人所述。
（2001），这个学习过程（不幸的是）并不总是导致均衡价格，但主要问题是这个拍卖师在大多数市场中并不存在！ 实际上，公司根据他们的知识和经验调整他们的价格（例如，Lesourne，1992）：因此，市场应该被建模为一个自组织过程。
近年来，自组织（即学习和进化）过程在经济理论中得到了广泛的研究，但主要是在博弈论框架中（例如，Fudenberg-Levine，1998，Weibull，1996）。 相反，在本文中，我们将市场模型视为嵌入多臂老虎机问题的非战略动态决策模型。
在与强盗问题相关的不完全信息经济模型中（例如 Aghion 等人。 1991, Arthur, 1993, Easley and Kieffer, 1988, McLennan, 1979, Rothschild, 1974, Schmalensee, 1975)，每个决策（即强盗）与收益的平稳概率分布相关，但该分布的参数未知 决策者，例如均值和/或方差。 已经进行了两种“解决”这个多决策问题的主要方法。
1）“贝叶斯最优”学习方法。
2）“自适应”学习方法。
在第一种方法中，决策者在未知参数上形成先验概率分布，使用贝叶斯规则对其进行修正，他的目标是最大化给定标准，通常是预期的折扣利润总和。 由于学习本身不是决策者的目标，因此完美识别未知参数的真实值对她来说可能不是最优的。 因此，从长远来看，她可能会选择次优决策，正如 Rothschild (1974) 所证明的那样。 从行为的角度来看，这种贝叶斯最优学习方法需要决策者具有高度的理性，因为她不仅要使用贝叶斯规则修改他们的信念，还要解决一个非常复杂的动态优化问题（参见 例如，伊斯利和基弗，1988）。
在第二种方法中，对决策者的理性要求要低得多，因为她只是遵循一个简单的“经验法则”，即她应用自适应算法（随机或非随机）来选择她的决定。 有趣的是，这种自适应五六十年代，数学家、心理学家和经济学家都对学习方法进行了研究。
– 由（应用）数学家，作为“解决”双臂（固定）老虎机问题的一种方式。 目的是设计一种自适应算法（具有有限的记忆），它可能是确定性的，如 Robbins (1952) 和 Robbins (1956)，或随机的，如 Samuels (1968)，它最大化选择的概率（在长期 跑）最好的强盗（参见 Cover 和 Hellman，1970 以及 Narendra 和 Thathachar，1989 第 3 章的概述）。
– 由心理学家，作为对观察到的人类行为进行建模的一种方式，例如“概率匹配现象”。 实验方案通常是一个简单的双臂老虎机问题（甚至是单臂老虎机），其中受试者被反复置于必须给出两种可能响应之一的位置，并且有两种结果，例如 ，“成功”和“失败”。 概率匹配现象是受试者匹配潜在概率的事实，即如果 p 是老虎机 1 中的奖励概率，那么经过一段时间后，受试者选择这个老虎机 1 的频率接近概率 2 p。
– 经济学家认为，作为模拟（所谓的）有限理性的一种方式，即当代理人不按照效用理论预测的方式行事时（见 Simon, 1959, p. 260261）。
这些关于学习（最优贝叶斯或自适应）的各种文献的共同点是决策者对其环境没有影响，因为它是静止的。 在 Rothshlid (1974) 或 Schmalensee (1975) 所考虑的市场定价双臂强盗理论中，垄断者随着时间的推移而学习，而假设客户的行为是静止的。 尽管如此，假设在典型的（零售）市场中，卖家（试图）学习他们的需求函数以最大化他们的利润，而客户（试图）学习最便宜的卖家以最小化他们的支出，这似乎是相当安全的。 结果，市场以非平稳的方式发展。 在本文中，我们提供了一个垄断定价的非平稳多臂老虎机理论，其中市场双方（垄断者和客户）随着时间的推移都在学习，因此市场的演化是一个自组织过程。
在我们的模型中，垄断者每次都从有限集合中选择一个价格，每个顾客随机但独立地决定是否访问垄断者的商店。 当给定的顾客在某个时间访问商店并且此时的价格对她来说是可以接受的，她会购买一个单位的商品。 在这种情况下，我们说她得到了“奖励”。 当她去商店但价格对她来说太高时，她不买，因此她“没有奖励”。 假设众所周知的（心理）效应定律，它断言事件“奖励”增加了重新发生的概率受保护的响应（参见例如，Staddon 和 Horner 1989），这意味着当客户访问并购买时，她会增加访问的可能性。 相反，当她访问但不购买时，她会降低访问的可能性。 使用行为心理学中使用的术语，“访问和不购买”事件被负强化，而“访问和购买”事件被正强化。 由于每个顾客光顾店铺的概率是时变的，垄断者的预期利润也是时变的； 因此，他面临着一个非平稳的多臂老虎机问题。
静止环境和非静止环境之间存在重要区别。 在静止的环境中，决策者总是可以将探索阶段与开发阶段分开。 结果，使用简单的停止规则（最优或非最优），他可以选择长期内最好的老虎机，概率任意接近 1。 不幸的是，正如我们将看到的，在非平稳环境中，不仅这种分离是不可能的，而且最佳老虎机的概念也未定义。
在本文的第一部分，我们为我们的非平稳多臂老虎机问题定义了一个事前最优决策，并讨论了在静态和非平稳环境中的学习。 在第二部分中，假设垄断者知道除了支付能力之外的一切，我们展示了一个基于购买行为的“计数学习规则”，它允许他获得足够的信息来计算最优价格。 在第三部分，我们放宽了垄断者除了支付能力之外什么都知道的假设。 因此，我们为垄断者分配了 Arthur (1993) 在多臂（固定）老虎机问题（Posch (1997) 也使用）中提出的随机强化学习规则，Hopkins and Posch (2005), Beggs (2005)) 等在博弈论框架中)，除了环境反馈之外不需要任何特定知识。 在这种情况下，如 Kirman 等人。 （2001）除其他外，市场的随机性反映了各种代理人的学习过程。 一开始，决策是随机做出的，但随着时间的推移，代理倾向于选择概率为 1 的决策。 我们的数值模拟表明，从长远来看： – 每位顾客光顾商店的概率为零或一。
– 垄断者可能会选择长期的次优价格。
市场确实可以锁定吸收状态，这种状态不仅从垄断者的角度来看是次优的，从客户的角度来看也是如此。 最后，基于数值模拟结果，我们展示了一个“容易学习”的环境，在这个环境中，垄断者总是选择长期的垄断价格。

2 模型

我们模型的（离散时间）动力学如下。 在每个时间 t，垄断者在以下有限集合中选择价格 P j > 0，扣除生产成本：
（1）
（2）
每个买家 i ∈ I ≡ {1, 2…N } 独立决定是否来店。 如果时间 t 的价格低于（或等于）她的支付意愿，那么决定来的买家现在将购买一单位商品，并且在相反的情况下不会购买。 令 n t ≤ N 为在时间 t 购买一单位商品的顾客数量。 因此垄断者的利润等于：
（3）
请注意，由于每个价格 P j > 0 都是扣除生产成本的，因此利润是非负的。
在时间 t 结束时，每个购买者调整她的访问概率，以了解她是否购买了该商品。
2.1 卖家的决策规则
每个买家 i ∈ I 的特征在于以下两个参数： 1) 支付能力 v i ∈ R + 。
2) 访问垄断者的自适应概率 θ i,t ∈ [0, 1]。
我们假设每个购买者的支付意愿是恒定的，这相当于说购买者的偏好随着时间的推移是稳定的。 然而，访问垄断者商店的概率会随着时间的推移而变化。 在他们早期关于购买行为随机模型的书中，Massy 等人。 (1970) 建议影响购买概率的因素是： - 经验，即过去购买的反馈。
– 外生市场力量的影响。
– 人口异质性。
在接下来的内容中，我们假设给定的客户在购买一件商品时倾向于更频繁地访问商店，而当她不购买时则更少。 购买概率仅根据个人经验进行修改，并且有是没有互动效应（即没有战略行为，没有模仿）和/或没有集体学习的可能性 3 。
令 P t ∈ P 是垄断者在时间 t 选择的价格，并且让 z i,t = 1 (z i,t = 0) 顾客 i 在时间 t 访问（不访问）商店的情况。
形式上，我们假设每个客户 i 使用以下随机强化算法来修改她访问 θ i,t 的概率：
（4）
其中 β i ∈]0, 1] 是一个参数。 这种强化算法在学习自动机文献中被称为线性奖励惩罚（参见例如 Narendra 和 Thathachar，1989 年）并且非常自然：当客户在时间 t 购买一个单位的商品时，她会增加访问的概率并降低访问的概率 当她不买。 给定学习规则[4]，从长远来看，可能会出现这样一种情况，一个顾客有可能会去商店，而另一个人最终会停下来拜访他，因为他经历了太多的高价。 重要的是： - {0} 是随机过程的吸收状态，但不是 {1}。
– 增量的大小是 β i 的递减函数。 给定关系 [4]，随机过程的增量 {θ i,t } 为：
（5）
因此，我们可以将 β i 解释为“反应性参数”。 β i 越高，客户的反应就越大，因为增量的幅度是 β i 的递增函数。
2.2 纯策略中的垄断价格：完整的信息案例
与大多数关于自适应学习的文献一样，我们将在本文中假设垄断者不会低估未来。 正如我们稍后将看到的，这意味着“勘探成本”为零。 为了在我们的动态市场模型中得出最优价格（即垄断价格），我们假设信息完整； 垄断者知道客户集合、支付能力 v i 、强化学习规则 [4]、学习参数 β i 和（如有必要）每个 i 的初始条件 θ i,0。 自从正如我们已经说过的那样，每个顾客 i 访问商店的概率不是恒定的，垄断者面临一个非平稳的多臂老虎机问题，这使得规范分析变得复杂，因为没有先验的自然方法来定义 最优价格。 我们将在这里关注纯策略中的最优价格。 在博弈论中，我们称纯策略为垄断者在每次 t ∈ N 时以概率 1 选择的决策（即价格 P j ∈ P）。让
(6)
是一组顾客使得他们的支付能力高于这个价格 P j 并且让
(7)
成为它的补充。 最后，让 Card I j 成为 I j 的基数。 不失一般性，我们假设卡片 I j 6 = ∅ 对于所有 j = 1, 2…J。
命题 1 假设所有 i 的 θ i,0 > 0。 如果 P j CardI j 6 = P k CardI k for j 6 = k，则在纯策略中存在唯一的（事前）最优价格。
证明：考虑垄断者在纯策略中选择价格 P j 的情况。 给定强化学习规则 [4] 并假设所有 i ∈ I θ i,0 > 0，属于 I j 的顾客会以概率 1 长期访问商店，而不属于 I 的顾客 从长远来看，j 不会以概率 1 拜访他。 这意味着：
(8)
因此，长期预期利润为：
（9）
（10）
如果所有 Π ∞ (P j ) 不同，则存在价格 P m ∈ P，即垄断价格，使得 Π ∞ (P m ) > Π ∞ (P j ) 对于所有 j 6 = m In 在完全信息的情况下，垄断者可以计算与每个价格 P j 相关联的长期（确定性）利润 Π ∞ (P j ) = P j Card I j ，因为他知道 Card I j 。 因此，他将在每个时间 t ∈ N 收取这个价格 P m。重要的是，找到（统一）垄断价格真正需要的不是v i 的知识，但只有所有 j 的 Card I j 的知识，也就是说，如果他们都在访问商店，有多少顾客以价格 P j 购买。 当然，如果允许垄断者进行价格歧视，即向不同的客户收取不同的价格，那么，完美的歧视将需要对 vi 的完全了解。
我们现在可以计算长期的（通常的）马歇尔总剩余 W ∞ (p m )，定义如下：
（11）
定义 W ∞ (P m ) 很重要，因为它定义了市场福利的规范基准。
2.3 固定和非固定环境中的学习：探索-利用权衡
我们现在假设垄断者没有关于他的环境的完整信息，特别是 vi 是未知的，但客户的数量和他们的强化学习规则 [4] 也可能是未知的。 当 θ i,t 对每个 i 随时间恒定时，垄断者的环境是平稳的，而当 θ i,t 随时间变化时，环境是非平稳的。
2.3.1 在固定环境中学习
考虑平稳的情况，例如在 Schmalensee (1975) 或 Arthur (1993) 中。 如果垄断者知道对于每个 i θ i 在时间上是恒定的，由于未来没有折扣，他的问题并不困难，因为他可以使用以下停止规则将探索阶段与开发阶段分开。
1）探索。 选择（连续）n ∈ N 次（n 有限）价格 P j，然后通过其经验平均值 Π j,n 估计（未知）预期利润。 重复 j = 1, 2…J。
2) 开发。 对于 t ≥ nJ，以概率 1 选择与最高经验均值相关的价格。
根据大数定律，他知道如果 n 足够高，他会以任意接近 1 的概率发现垄断价格。 因此，在静止的环境中，垄断者可以表现得像古典（甚至贝叶斯）统计学家。
特别是，不需要使用一些随机自适应算法。 重要的是要认识到 n 可以任意大，因为勘探成本为零，因为未来不会被假设打折。 当未来被打折时，给定一个优化标准，选择 n“高”可能不是最优的。 Rothschild (1974) 从贝叶斯学习的角度明确考虑了固定两臂老虎机问题中的折扣情况，其中决策者的目标是最大化预期的贴现利润总和。 他表明，存在一个最优停止规则，可以最好地解决勘探-开发冲突，并且这个最优停止规则可能导致决策者经常无限地选择次优价格。 从长远来看，这个结果 4 在经济学文献中被称为不完全学习。
在平稳的环境中，当未来不打折时，只要尝试了所有价格，决策者是以价格 P 1 还是 P J 开始探索阶段都没有关系。 完成此操作后，在任意接近 1 的概率下，垄断者将在探索阶段之后（永远）选择垄断价格。
Schmalensee (1975) 和最近的 Arthur (1993) 考虑了一个固定的多臂老虎机问题，其中垄断者使用一些随机强化算法。 他们表明，一般来说，垄断者不会发现长期的垄断价格：在正概率下，他最终会无限地经常选择次优价格 5 。 在平稳的框架中，这种随机强化算法不是很有说服力，因为我们可以使用上述简单的统计决策规则轻松找到最优价格。 正如我们现在将看到的，当环境是非平稳的时，这样的停止规则是无法实现的，这意味着随机强化学习可能会在非平稳环境中找到它的根源。
2.3.2 非平稳性：“外生”与“内生”
如果平稳环境是清晰的，非平稳环境就不是。 正如我们将看到的，非静止环境有时可能确实是静止的！ 在多臂老虎机问题中，如果给定老虎机的概率分布与时间无关，则环境对于决策者来说是静止的。 在一个简单的双臂老虎机问题中，每个老虎机 i 是参数 θi 的伯努利分布，i = 1, 2（即“成功”的概率），平稳性意味着 θi 与时间无关。 相反，如果 θ i 是时间相关的，即如果 θ i 可能随时间变化，则环境是非平稳的。 但是 θ i 可能会以许多不同的方式随时间变化。
非平稳性的“外生”形式是参数根据“外生特定规则”从时间 t 演变到时间 t + 1 的情况。
在他们关于“学习自动机”的书中，Narendra 和 Thathachar 6 (1989) 区分了两种形式的（外生）非平稳环境：
1）马尔可夫切换环境。
2) 状态相关的非平稳环境。
马尔可夫切换环境可能是 θ i,t 遵循简单马尔可夫链的环境，例如，θ i,t ∈ {0.2, 0.6} 和 P(θ i,t+1 = 0.2|θ i,t = 0.2 ) = p i 和 P(θ i,t+1 = 0.6|θ i,t = 0.6) = q i 。 依赖于状态的非平稳环境可能是 θ i,t 演化的环境，可以说是时间的确定性函数。 例如，对于某个（固定）函数 f，θ i,t+1 = f (θ i,t ) 使得 f (θ i,t ) ∈]0, 1[ 对于所有 t。
在这两种形式的环境中，非平稳性是外生的，因为决策者对其环境没有任何影响。 实际上，环境被标记为非平稳是因为参数 θ i,t 随时间变化，但参数的演化规律是平稳的，即马尔可夫链的转移矩阵和函数 f 是时间无关的，并且 确实是外生的。 人们甚至可以认为转移矩阵和函数 f 是时间相关的，只要它们的演化定律是平稳的。
非平稳性的“内生”形式要困难得多，它涉及“系统”（即游戏、市场、社交网络……）的演变，这是许多相互依赖的决策过程的结果。 让我们举两个众所周知的例子。
– El-Farol 酒吧问题 7，假设每个星期天有 N（例如，N = 100）人去酒吧（El-Farol）。 每个人独立决定是否访问酒吧。 问题是酒吧很小，每个人都不喜欢在拥挤的时候呆在那里。 如果说超过 70% 的人去酒吧，那里很拥挤，每个人都比呆在家里更糟糕。 相反，如果不到 70% 的人去酒吧，每个人都喜欢在那里，也就是说，来不后悔。 给定一个学习规则，让每个人根据在第 n 周去酒吧的人口的已知 8 频率来决定是否在第 n + 1 周来，这个系统的进化是（内生的）非平稳的，因为 每个人的决策过程取决于酒吧中人的百分比，这本身取决于每个人的决策过程。
– 重复的“平均游戏 9”，其中 N 人每次必须选择 0 到 100 之间的一个数字，获胜者是选择最接近所有选择数字的平均值乘以参数 p 较低的数字的人 ( 或等于）到一个 10 。 在每场比赛结束时，会公布获胜者号码。 给定一个学习规则让每个玩家根据游戏 n 的结果为游戏 n + 1 选择一些数字，这个系统的进化是（内生的）非平稳的，因为每个人的决策过程取决于获胜者数量，获胜者数量本身 取决于每个人的决策过程。
假设每个智能体都有一个固定的（自适应）学习过程，建模者（可能知道各种学习过程）仍然不知道支配系统演化的规律。 这就是我们谈论内生非平稳性的原因。
一般来说，对于这样的系统，演化（强烈）依赖于路径，并且存在许多（可接受的）“静止状态”。 这样的系统通常称为自组织过程。

2.3.3 在非固定环境中学习
现在考虑 {θ i,t } 随时间演变的情况，如等式（4）所述，并假设垄断者通过（连续）收取 n 次最高价格 P J 来开始探索阶段。 如果 n 足够高，则可能在探索阶段结束之前，不属于 I J 的客户将不再访问商店。 由于 {0} 是随机过程 {θ i,t } 的吸收状态，因此属于 I J 的客户将是探索阶段后唯一剩下的客户。 在这种情况下，P J 成为“事后”最优价格，但通常不等于事前最优价格。 一个更好的想法可能是以最低价格 P 1 开始探索阶段，然后是 P 2 等等，但是如果尝试所有价格，这显然会导致他遇到同样的问题。
因此，在静止环境和非静止环境之间存在根本区别，即在非静止环境中存在不可逆效应 11 （或锁定效应）。 这种不可逆效应意味着不可能将探索阶段与利用阶段分开，因为收集信息过程会影响学习对象，或者换句话说，学习会影响要学习的内容。 这个问题在博弈论中是众所周知的（参见例如 Fudenberg-Levine (1998)），但据我们所知，在多臂老虎机问题中却不是（参见 Banks 等人，1997）。 有趣的是，我们最近发现，许多心理学家、神经科学家和生物学家都在研究静止和非静止环境中的探索-探索权衡。
在 Daw 等人。 （2006 年）（另见 Cohen 等人，2007 或 Groß 等人，2008），他们考虑了一个非平稳多臂老虎机问题，其中平均收益在每次试验中随机且独立地变化。 他们考虑以下三个学习过程。
– -贪婪规则，其中决策者以概率 (1− ) 选择强盗（被认为）是最好的，并以概率 选择另一个强盗。
– soft-max 规则，根据其相对性能或估计的期望值随机选择一个老虎机。
– 一个“修改过的”soft-max 规则，其中未被选中的老虎机将获得“奖励奖金”，从而增加其被选中的概率。
Daw et al., (2006) 发现了经验（强有力的）证据表明受试者（在他们的实验中）使用了 soft-max 规则。

3 通过计数学习：只有客户的支付能力是未知的

我们将在本节中假设只有支付 vi 的能力是未知的。 特别是，方程 [4] 给出的强化算法连同参数 β i 、所有 i 的初始条件 θ i,0 和客户数量都被假定为垄断者已知。 在这种不完全信息设置下，给定一组价格 P，如果只有 vi 未知，决策者如何找到垄断价格 P m？
找到垄断价格的一种自然方法是从客户的购买行为中推断（即学习）卡 I j。 请注意，这在某种意义上等同于（旧的）显示偏好问题，其中人们试图从购买行为中推断（不可观察的）偏好。 例如，如果给定的客户 i 以给定的价格 P j c 购买，但没有以 P j+1 的价格购买，垄断者可以推断 i ∈ I j ∩ I j+1 。 给定价格集合 P，知道 i ∈ I j ∩ I j+1 等价于知道 v i 。 正如我们之前所说，这里真正需要的不是对 vi 的完美知识，而只是 Card I j 。
假设垄断者收取给定价格 P j 。 如果所有顾客都到店，他只需统计以该价格购买的顾客数量即可获得 Card I j 。 如果他可以对所有 j = 1, 2…J 做到这一点，他将能够计算每个 j 的相关利润 P j Card I j。 然而问题并不那么简单，因为垄断者面临一个非平稳问题：如果他连续多次收取给定价格 P j ，则属于 I j c 的客户可能会以 1 的概率消失。 我们现在将提出一个“计数规则”，当学习参数 β i 对所有 i 足够小时，它允许垄断者为所有 j 推断 Card I j。
我。
计数规则
**1) 忠诚度提升过程：**连续 n 次（n 有限）收取最低价格 P 1 。
**2）统计过程：**在时间n+j，j=1，2…J-1，收取价格Pj+1，统计以该价格购买的顾客数量。
当 n 足够高时，在增加忠诚度的过程结束时，属于 I 1 的所有顾客访问商店的概率任意接近 1。 现在，在清点过程中，（至少）I 1 ∩ I 2 c 的所有顾客到店时都没有购买该商品。 因此，从时间 t = n + 1 到时间 T = n + J - 1，对于所有 i ∈ I 1 ∩ I 2 c ，θ i,t 是 t 的减函数。 然而，在 β i 足够小的特定情况下，属于 I 1 ∩ I 2 c 的顾客在时间 T = n + J - 1 时仍会以任意接近 1 的概率访问商店。这是 命题2的基本思想。
命题 2 假设垄断者使用上述计数规则。 为简单起见，我们假设 θ i,0 = θ 0 和 β i = β 对于所有 i ∈ I。给定一组价格 P, 1 i J−1 h ) ln( 2(1−θ 0 ) 1− 和 n ≥ , 在时间 ∀ > 0 (with < 2(1 − θ 0 )), 如果 β ≤ 1 − 2 2− ln(1 − β) T = n + J − 1, 那么 θ i,t ≥ 1 − , ∀i ∈ I 1 , ∀t ∈ {n + 1, …n + J − 1}；计数过程可以以任意接近 1 的概率精确完成。
证明 见附录。
获得相同结果的另一种方法是考虑参数 β i,t 是所有 i 的时间 t 的递减函数的情况。 如果我们像 LambertonPagès-Tarrès (2004) 中那样假设：
（）
我们还可以证明存在一个有限的 n，使得计数过程可以以任意接近 1 的概率精确完成。
我们之前已经看到，随机过程增量的大小 (θ i,t ) t∈N（参见方程 [5]）是 β i 的增函数。 假设 β i 非常小，就相当于说学习过程非常缓慢。 当增加忠诚度的过程完成时，所有访问商店的概率任意接近一。 由于所有的 β i 都非常小，垄断者可以尝试所有的价格，就好像访问的各种概率是恒定的一样，这就是垄断者可以从购买行为中推断出 Card I j 的原因。
当各种 β i ∈]0, 1[，即不一定很小，假设所有 i 的 θ i,0 > 0，他仍然可以使用下面的计数规则。 让任意小> 0。

1. 连续收取最低价格 P 1 的 n 倍，使得 θ i,n > 1 - 对于所有 i （请注意，对于所有 i 和 ，n 是 θ i,0 和 β i 的函数）
2. 在时间 n + 1，收取价格 P J 并统计以该价格购买的客户数量，即获得卡 I J
3. 现在连续收取 n J ≥ 1 倍最低价格 P 1 使得概率 θ i,n+n J +1 > 1 - 对于所有 i
4. 在时间 n + n J + 2，收取价格 P J-1 并计算以该价格购买的客户数量，即获得卡 I J-1
5. 现在收费 n J−1 ≥ 1 倍最低价格 P 1 使得概率 θ i,n+n J +2+n J−1 > 1 − 对于所有 i
6. 重复直到卡片 I j 对所有 j.
   当然，从购买行为中学习 Card I j 的可能性关键取决于对支付能力 vi 的完善知识和客户的学习规则。 在实践中，不清楚为什么应该知道支付能力。 当垄断者对客户的特征一无所知时，由于他观察到与他收取的价格相关的利润，他仍然可以使用软最大规则的一个版本来（尝试）学习垄断价格。 这就是我们现在要研究的。

4 强化学习：垄断者可能“完全无知”

4.1 强化学习规则
在一个静止的多臂老虎机问题中，我们看到决策者可以首先估计未知参数（通常是均值），然后选择具有最高估计均值的价格。 使用这个停止规则将允许他以任意接近 1 的概率发现最优价格。 然而，在非平稳情况下，如我们之前所见，这样的停止规则不起作用，因为决策者无法将探索阶段与开发阶段分开。 在这样的环境中，“解决”问题的一种方法可以使用 soft-max 规则来实现，即随机决策规则。 尽管有很多候选者，我们还是选择了 Arthur (1993) 提出的随机自适应算法。
令 S j,t-1 是在时间 t-1 分配给价格 P j 的强度，并假设 P j 是时间 t 的选择价格，并且 n t 个客户在时间 t 购买了一个单位的商品。
令 Π j,t = P j .n t 为垄断者在时间 t 的利润。 （简单）自适应规则如下：
（12）
（13）
每个价格的强弱反映了它过去的表现，即它的累计利润。
由于我们的垄断者无法将探索阶段与开发阶段分开，因此很自然地假设他使用了一种自适应随机规则，该规则允许他“探索和利用”。 令 η j,t 为每个时间 t 的归一化强度：
（14）
由于 η j,t 是标准化权重，我们现在假设垄断者在时间 t 以等于 η j,t 的概率随机抽取给定价格 P j。 由于 η j,t 根据价格 P j 的表现随时间演变，这种随机强化算法可能是一种“解决”开发-探索权衡的方法。
在我们的模型中，Π j,t ≥ 0 意味着 η j,t ≥ 0。如果 Π j,t 可能为负，η j,t 也可能为负，我们的强化算法将无法工作。 然而，当 Π j,t 可以为负时，仍然可以使用我们的随机强化规则的以下“logit”版本，如 Kirman 等人 (2001) 等：
（15）
其中λ是一个参数。 当然，这种强化算法取决于参数 λ，而我们使用的算法是无参数的。
备注 12。 客户的强化学习规则（由方程 [4] 给出）和垄断者的强化学习规则（由方程 [12] 到 [14] 给出）是不同的。 垄断者的学习规则与决策的绩效（即利润）成正比，而客户的学习规则与访问决策的绩效（即盈余）不成正比。 令 S i,1,t 为与客户 i 的“拜访”决策相关的强度 (
（16）
（17）
其中 P t ∈ P 并且让
（18）
是客户 i 在时间 t 访问商店的概率，其中 β i 是一个参数。
当(v i - P t ) > 0 时，即当客户i 拜访并购买时，她的拜访概率增加，而当(v i -P t ) < 0 时，其拜访概率降低。 在这样的模型中，客户和垄断者的决策规则都与“绩效”成正比。
4.2 相关文献
我。 他们使用平均场近似方法研究随机过程的渐近行为。 虽然这不是严格意义上的概率证明，但这提供了一种有趣的简单计算方法来研究随机过程的长期行为。 与老虎机问题相关，Lamberton 等人 (2004) 提供了当决策者使用线性奖励不作为随机算法但在静止环境中时 2 臂老虎机问题的渐近行为的严格概率证明。 Arthur (1993) 使用线性奖励不作为算法 (14) 研究了一个静止的多臂老虎机问题，其中使用重整化序列 C t = C t v 对强度进行重整化（另见 Laslier-Topol-Walliser 2001）。 Arthur (1993) 表明，当 0 < v < 1 时，随机过程以正概率收敛到单纯形的非最优顶点，而当 v = 1 时，它以概率 1 收敛到最优顶点。 在证明中，Arthur (1993) 依赖于 Pemantle (1990) 的一个非常一般的定理。 Hopkins 和 Posch (2005) 在博弈论框架中研究了 Arthur (1993) 使用的算法，并讨论了 Pemantle (1990) 定理的适用性（另见 Beggs (2005) 和 Pementle (2007)）。 他们认为 Arthur (1993) 定理可能是正确的，尽管证明不正确，因为他依赖于 Pemantle (1990) 定理而条件不满足。 我们不会进一步讨论这些技术细节，因为我们在本节中只提供数值结果。
4.3 数值结果
4.3.1 概述
我们将从数值模拟的角度研究市场行为。
令 η t = (η 1,t , …η J,t ) ∈ Δ(R J )，其中 Δ(R J ) 是 R J 的单位单纯形， θ t = (θ 1,t , …θ N,t ) ∈ [0, 1] N 。 让
(19)
其中 (η t , θ t ) 是我们随机过程的状态向量，Δ(R J ) × [0, 1] N 是状态空间。 在每个样本路径上，我们的数值模拟表明随机过程的长期行为具有以下两个属性： – 所有客户的概率为零或一； – 垄断者选择概率为 1 的价格。
这意味着从长远来看，市场的演变是确定性的：垄断者选择概率为 1 的价格，而所有客户的概率为 1 或 0。 要理解这个数值观察背后的直觉，请注意增量的大小.
– Δθ i,t 是静止的。
自适应规则 (12)，因为 X – Δη t 不是静止的。 原因很简单：假设 X S j,t 是时间 t 的增函数，对于给定的利润 Π j ，S j,t 越高，j j 的增量 Δη t 越低。 因此，过程 η t 的增量是时间 t 的递减函数。
从行为的角度来看，这意味着客户的“反应性”随着时间的推移是恒定的，而垄断者的“反应性”是时间 t 的减函数。 虽然垄断者在中间运行中仍然以正概率选择每个价格，但顾客倾向于分成两组： – 以概率 1 访问商店并购买商品的人 13； ——消失的人。
回想 {0} 是随机过程 (θ i,t ) t∈N 而不是 {1} 的吸收状态，正如我们所说，可能是这样的情况，即客户以相等的概率来（并购买） 在中间运行时变为一个，但从长远来看最终会消失。 这个特征来自市场的路径依赖特性。
我们在考虑以下想法的情况下进行了数值模拟。 当与垄断价格相关的利润不足以高于所有其他价格时，决策者可能难以在每条样本路径上发现长期价格 P m。 因此，我们研究了两种情况，一种是学习“困难”，一种是学习“容易”。 我们在这两种情况下都选择了以下参数：
– J = N =5
– P i = v i ，其中 v i ∈ R + 但对于所有 i 都是有限的
– β i = 0.2
– θ i,0 = 0.5 对于所有 i
– S j,0 = 1 ⇐⇒ η j, 对于所有 j，0 = 0.2。
4.3.2 学习“难”的案例
正如我们之前所说，当与每个价格相关的利润彼此非常接近时，学习是“困难的”。 困难学习的自然候选者是各种价格在 0 和 1 之间的情况，即：
(20)
考虑以下一组价格。
(21)
因此很容易检验垄断价格是否为
(22)
根据历史，我们观察到垄断者在长期中选择 P 的价格，除了 P 1 = 0.12。 对于不可忽略的样本路径部分，垄断者在长期内选择价格 P 5，因此，客户 5 是唯一剩下的客户。 原因在于市场动态的自我强化特性：价格 P 5 的选择概率越高，在其他条件不变的情况下，客户 1 到 4 的访问概率越低。但访问的概率越低。 客户 1 到 4 的访问，价格 P 5 的选择概率越高，因为 P 5 成为最优价格。 请注意，当垄断者长期选择这个价格 P 5 时，从客户的角度来看，这个静止状态是高度次优的，从垄断者的角度来看也是如此。 与垄断价格相关的马歇尔总剩余为 W (P m ) = 0.75 + 1.4 = 2.15，而在静止状态下为 W (P 5 ) = 0.85。 福利损失如此之大！
这种负面结果在于学习是“困难的”，因为与每个价格相关的利润彼此非常接近。 因此，垄断者使用的自适应算法无法区分最优价格与其他 14。 如果与垄断价格相关的利润远高于其他价格，则自适应算法（也许）会在长期内发现它。 现在让我们考虑这种情况。
4.3.3 学习“容易”的案例
考虑以下一组价格。
(23)
很容易检验 P 5 是垄断价格。 在这种情况下，一旦选择了 P 5，动态就会自我强化，垄断者会很快以接近 1 的概率选择 P 5。 为了更清楚地看到这一点，假设在日期 t = 0 选择了 P 5 并且客户 5 在这个时间 15 来访问商店。
由于只有客户 5 购买商品，垄断者的利润等于 P 5 = 10。使用自适应规则 (12) 并给定初始条件 S j,0 = 1 对于所有 j，垄断者将选择价格 P 5 在时间 t = 1 时，概率等于 (11/15) ≈ 0.73：然后动态变得自我强化。 因此，在每条样本路径上，我们观察到垄断者在长期内选择（最优）价格 P 5 = 10。 当然，这是一个简单的案例，因为以这个价格实现的利润远高于其他所有价格。
现在考虑一组价格 P’，但其中 P 5 ∈]0.53； 10[。 显然，当 P 5 从 10 下降到 0.53 时，学习变得越来越困难，因为在其他条件不变的情况下，与最高价格 P 5 相关的利润变得更低。 正如我们之前所见，当 P 5 = 0.75 时，垄断者并不总是能够将 P 5 = 0.75 的最优价格与其他价格区分开来。 相反，当 P 5 = 10 时，垄断者总是能够区分最优价格。 因此很自然地要问是否存在“临界”价格 P * 使得： – 如果 P 5 ≥ P * ，则始终选择长期垄断价格。
– 如果 P 5 < P ∗ ，垄断价格并不总是在长期内被选择。
我们已经对许多价格进行了数值测试，我们发现这个临界价格是（大约）P * = 1.9，这意味着当我们考虑价格集合 P 0 = {P 1 = 0.12; P 2 = 0.35； P 3 = 0.42； P 4 = 0.53； P 5 }，只要 P 5 > 1.9，垄断者总是发现长期的垄断价格。
现在很自然地要问这个临界价格 P * = 1.9 是否对环境的扰动具有鲁棒性。 为此，可以进行许多扰动。 例如，on 可以更改价格 P 4 或客户数量或价格数量，例如通过添加另一个价格 P 0 。 正如我们将看到的，这个临界价格通常对这种扰动并不稳健。 请注意，在以下所有情况下，P 5 都是最优价格。

1. 现在考虑一组价格
   (24)
   其中，除 P 4 外，只有一个客户满足 v i = P i 。 对于价格 P 4 ，现在有 3 个客户，他们的支付能力为 0.53。 数值模拟表明，垄断者无法发现长期垄断价格：长期可能选择 P 4 或 P 5。 因此，1.9 不再是关键价格。
2. 令 P i = v i for i = 1…5 与前一种情况一样。 但是，我们现在下面的一组价格
   .(25)
   在此示例中，当客户 5 访问商店时，价格 P 0 和 P 5 与其他价格相比提供（高）利润。 数值模拟表明，从长远来看，垄断者可能会选择 P 0 = 1.8 和 P 5 = 2。 因此，1.9 不再是关键价格。
3. 考虑以下一组价格，其中所有 i 的 P i = v i。
   (26)
   当 P 4 = 0.53 时，我们回到之前的环境，我们知道垄断者会发现最优价格。 然而，当 P 4 = 0.9 时，数值模拟表明，垄断者最终可能会选择长期价格 P 4 = 0.9。 因此，1.9 不再是关键价格。
   从根本上说，这种稳健性的练习表明，垄断者使用的随机算法只有在与最优价格相关的“性能”远高于所有其他算法时才有效。 如果不是这种情况，从长远来看，可能会选择次优价格。 在固定设置中，一种获得最优价格收敛的方法，如 Arthur (1993) 所述，可能是通过重整化序列降低学习过程的速度。 不幸的是，在非固定环境中，这不起作用，因为学习过程以路径依赖的方式影响要学习的内容。 正如 Cohen 等人 (2007) 在他们的论文中所说：“迄今为止，还没有描述过如何在非平稳环境中的探索和利用之间进行权衡的普遍最优算法，而且尚不清楚这样做是否可行 。” Cohen 等人，(2007) 第 935 页。
   我们用不同的价格对这个市场模型进行了多次模拟，我们市场的“定性”行为始终保持不变：从长远来看，每个客户的概率为 0 或 1，垄断者选择的价格为 概率一。

5 结论

我们相信我们的“简单”框架很有趣，因为它强调了自适应随机算法在非平稳环境中的使用，即不可能将开发阶段与探索阶段分开。 当垄断者知道除了支付能力之外的一切时，我们已经证明垄断者可以通过使用计数规则从购买行为中推断出推断最优价格所需的所有信息。 当他对客户的特征“完全无知”时，可以通过使用自适应随机算法来获得学习最优价格的自然方法，其中选择给定价格的概率与其（过去的）表现成正比。 当不同价格的表现足够“接近”时，垄断者最终可能会在长期内选择次优价格，因为算法无法将最优价格与其他价格区分开来。 在最优价格的表现远高于其他所有的特定情况下，垄断者将在长期内选择这个价格。
我们的结果确实是数值的，而不是分析的。 因此，仍然需要证明我们的市场随机过程的“收敛性”，还需要设计一种自适应随机算法，使垄断者能够以概率一选择长期的最优价格。 据我们所知，我们不知道任何可以用来证明我们的市场模型“收敛”的一般定理，因为涉及自适应随机算法的模型在数学上是困难的（例如，参见 Pemantle，2007）并且严重依赖于 考虑的随机算法（参见例如，Lamberton et al., 2004）。