1. 项目概述:当在线交易遇上经典秘书问题
最近在优化一个高频交易系统的决策模块时,我又把经典的“秘书问题”翻出来琢磨了一遍。这个老问题说的是,你要从N个依次到来的候选人中选一个最好的当秘书,但面试完一个就得立刻决定是否录用,录用了后面的就不能再看了,目标是最大化选到最佳人选的概率。这听起来像个有趣的数学游戏,但在真实的在线交易场景里,它摇身一变,成了一个更刺激也更现实的“在线交易秘书问题变体”。
想象一下这个场景:你面前有一个资产的价格序列,它正一个接一个地到来。你的目标是在这个序列结束前,选择一个价格点进行“卖出”操作(或者对称地,选择买入点),以最大化你的收益。和秘书问题一样,你只能看到当前和历史的价格,对未来的价格一无所知;一旦你决定在某个价格点卖出,交易就立刻执行,后续无论价格涨到多高都与你无关了。这本质上就是一个“在线决策”问题——你必须在信息不完全的情况下,做出不可撤销的决定。
这个变体之所以吸引我,是因为它剥离了预测市场的幻想,直击交易决策的核心困境:如何在“等待更好机会”和“害怕错过当前机会”之间找到最优的平衡点?我们设计的算法,目标不是预测价格,而是设计一套应对不确定性的规则,并用量化的“竞争比”来评估其最坏情况下的表现。所谓竞争比,简单说就是:哪怕市场以最不利于你的方式(即事后看,最优卖出点出现在你最不可能选中的时候)给出价格序列,你的算法获得的收益,与全知全能者(知道所有未来价格)获得的最优收益之比,也不会低于某个值。这个值越高,说明算法越稳健。
而这次要聊的成果,正是在这个框架下取得的一个有趣突破:一个算法同时实现了强竞争比3.523和弱竞争比2。别小看这两个数字,它们代表了两种不同的评价维度。强竞争比要求算法在任何时候、面对任何价格序列都满足这个性能保证,非常严苛;而弱竞争比则允许算法在价格序列的“长度”(即总观察期N)趋于无穷大时渐进地满足性能保证,条件宽松一些,但往往能达成更好的理论极限。一个算法能同时在这两个指标上达到优秀水平,意味着它在短期和长期的稳健性之间取得了很好的折衷。接下来,我就把这个算法的设计思路、核心技巧以及我在模拟中踩过的坑,掰开揉碎了和大家聊聊。
2. 问题建模与竞争比概念深析
2.1 从经典秘书问题到在线交易变体
经典秘书问题的设定很干净:N个候选人,能力值是一个从1到N的排列(即没有并列),顺序随机。你面试完第i个后,必须立刻决定是否录用,录用则游戏结束,拒绝则永不回头。目标是最大化选到排名第一(即能力值为N)的候选人的概率。最优策略是“观察前r个,然后录用第一个比前r个都好的”,当N很大时,最优的r约等于N/e,此时选到最佳的概率也约等于1/e(约36.8%)。
但在线交易变体(有时被称为“在线搜索”或“单样本选择”问题)有几个关键变化,让问题变得更复杂也更有实际意义:
- 价值连续而非离散:价格是连续值(或来自一个连续分布),而不仅仅是排名。这意味着“历史最佳”是一个具体的数值,比较不再是排名比较,而是数值大小比较。
- 目标函数变化:目标不再是“选到最大值”的概率,而是最大化所选价格值本身(或与某个基准的比值)。更常见的是,我们关注的是竞争比。假设全知最优解(即事后看到的所有价格中的最大值)是
OPT,你的算法选出的价格是ALG,那么竞争比c满足ALG ≥ OPT / c。我们的目标是设计算法,使竞争比c尽可能小(最好能接近1)。 - 价格模型:为了理论分析,通常假设价格来自一个未知的、有上下界的分布。最简单也最常用的模型是“价格落在已知区间
[m, M]内”,但m和M的具体值未知。这就是所谓的“无先知”假设——你只知道价格有界,但不知道界限在哪。
我们讨论的变体,通常称为“基于样本的价格交易”或“带观察期的秘书问题”。其标准流程是:
- 总共有
N个价格依次到来p1, p2, ..., pN。 - 算法可以将整个过程分为两个阶段:观察阶段和行动阶段。
- 在观察阶段(例如前
τ个价格),算法只能观察并记录价格,不能进行交易。 - 从第
τ+1个价格开始,进入行动阶段。此时,算法可以基于观察阶段获得的信息(比如观察期内的最高价M_obs),设定一个阈值或决策规则。当第一个满足该规则的价格出现时(例如,第一个超过φ * M_obs的价格),算法必须立即接受并交易,游戏结束。
2.2 强竞争比与弱竞争比的本质区别
这是理解本文算法价值的关键。很多文献只讨论其中一种,能同时优化两者的算法设计更有挑战性。
强竞争比:要求对于每一个有限的价格序列长度N,算法都保证竞争比不超过某个常数
c_strong。也就是说,无论市场只给了你10个价格,还是1000个价格,你的算法在最坏情况下的表现都有统一的理论上界担保。这非常严格,因为它要求算法对任何“游戏长度”都鲁棒。设计高强竞争比算法的难点在于,你需要防范那些专门针对你的算法参数τ而构造的“短序列攻击”。例如,如果你的观察期τ设得较长,对手可以构造一个序列,让最大值恰恰出现在观察期内,让你永远错过。弱竞争比:只要求当价格序列长度
N趋于无穷大时,算法的竞争比不超过某个常数c_weak。即lim sup_{N→∞} (竞争比) ≤ c_weak。这放松了对有限N,特别是小N情况下的性能要求。因此,弱竞争比的理论下限通常可以比强竞争比更低(即更接近1,性能更好)。设计弱竞争比算法时,我们可以更自由地选择τ作为N的函数(例如τ = N/e),从而利用大数定律等渐进性质。
一个生动的类比:强竞争比好比要求一个运动员在每一场比赛中都至少拿到铜牌,无论比赛是社区赛还是世锦赛。弱竞争比则好比要求该运动员在参加足够多的高水平比赛(如世锦赛、奥运会)后,其长期平均成绩能达到银牌水平,但允许他在某些小型比赛中发挥失常。显然,同时保证“每场必拿铜牌”和“长期可达银牌”是更厉害的成绩。
我们这次设计的算法,其精妙之处就在于通过一种自适应的阈值策略,巧妙地应对了有限N和无限N的不同挑战,从而同时获得了c_strong ≈ 3.523和c_weak = 2的保证。3.523这个数字不是凭空来的,它与数学常数e和黄金分割比例有关,是此类问题强竞争比的一个已知优秀界限。而2则是弱竞争比的一个经典且紧的下界(即不可能设计出弱竞争比小于2的算法),能达成2,说明我们的算法在渐进意义下已经达到了最优。
3. 算法核心设计:双阈值与自适应观察期
直接上干货。算法的核心思想是不要把所有鸡蛋放在一个篮子里,具体来说,是不要只依赖一个固定的观察期或一个固定的阈值倍数。我们设计了一个两阶段的阈值策略,并且让观察期的长度根据实际情况动态调整。
3.1 算法步骤详解
假设价格序列为p1, p2, ..., pN。算法维护几个关键变量:
M_obs:当前观察阶段内看到的历史最高价。threshold_1,threshold_2:两个动态更新的价格阈值。- 一个状态机,标识当前处于哪个决策阶段。
步骤1:初始观察与第一阈值设定算法从一个初始的、较短的观察期开始。这个观察期的长度τ1不是固定的,而是一个关于N的保守函数,例如τ1 = floor(√N)或一个很小的固定比例(如0.1N)。这个阶段的目标是快速获取市场价格的初步范围,避免在完全无知的情况下行动。在此阶段,我们只是记录M_obs,绝不交易。
观察期结束后,我们设定第一个阈值:threshold_1 = φ1 * M_obs。这里的φ1是一个大于1的常数,它的选取直接关系到强竞争比。通过理论推导(涉及最坏情况分析),可以得出φ1的最优值约为1 + √( (e-1)/e ) ≈ 1.648。这个值确保了,即使最大值出现在早期观察期,我们后续也有合理的阈值去捕捉“次优”的机会。
步骤2:第一阈值行动阶段从第τ1+1个价格开始,我们进入“狩猎”状态。如果遇到第一个价格p_k ≥ threshold_1,我们不会立即接受,而是进入一个“待定”状态。这是与传统策略最大的不同。
步骤3:第二阈值设定与最终决策当我们遇到第一个超过threshold_1的价格p_k时,我们用它来更新我们的信息!我们将p_k与之前的M_obs比较,取较大者作为新的参考基准M' = max(M_obs, p_k)。然后,我们设定一个更激进(更低)的第二阈值:threshold_2 = φ2 * M'。这里φ2通常小于φ1,甚至可能小于1(即允许我们接受一个比历史最高低的价格)。φ2的选择目标是优化弱竞争比。
紧接着,从p_k的下一个价格p_{k+1}开始,我们寻找第一个满足p_j ≥ threshold_2的价格。一旦找到,立即接受p_j并完成交易。
如果直到序列结束都没有价格触发threshold_1或threshold_2怎么办?这就是算法的保底机制:我们必须接受最后一个价格p_N。这保证了算法在任何情况下都不会“空手而归”,这是满足竞争比定义的必要条件。
3.2 参数选择与理论依据
为什么这样设计能同时保证强竞争比和弱竞争比?
强竞争比 (3.523) 的保证:关键在于
φ1 ≈ 1.648和第一阶段的观察期τ1。通过严谨的最坏情况分析(通常使用“对手论证”),我们可以证明,无论对手如何构造一个长度为N的序列,我们算法的收益与OPT的比值都不会超过一个由φ1和τ1/N决定的上限。通过优化这个上限函数,我们可以得到全局最小值点,对应的竞争比就是约3.523。τ1的选择需要足够小,以避免在短序列中浪费太多机会,但又不能太小,否则M_obs没有统计意义。floor(√N)是一个在理论和实践中都表现良好的折中选择。弱竞争比 (2) 的保证:当
N → ∞时,我们的策略实际上退化(或进化)为一个更高效的策略。在渐进情况下,我们可以让初始观察期τ1的长度也趋于无穷(但增长速度慢于N,例如τ1 = o(N))。这样,观察期得到的M_obs以概率1收敛于价格分布的上界M(在未知上下界模型中)。此时,第一个阈值threshold_1 ≈ 1.648M会变得非常苛刻,几乎没有任何价格能达到。但我们的策略妙就妙在第二阈值。 当N很大时,几乎可以肯定,会有一个价格p_k落在[M/φ1, M]这个区间内(因为φ1>1,这个区间非空)。这个p_k会触发我们的第一阶段,并让我们将参考基准更新为M',它非常接近M。随后,我们设定threshold_2 = φ2 * M' ≈ φ2 * M。如果我们选择φ2 = 1/2,那么threshold_2 ≈ M/2。 现在,关键来了:在无限长的序列中,价格落在[M/2, M]区间内的概率是正的。因此,在p_k之后,我们以概率1会遇到一个价格超过M/2。而我们最终接受的价格p_j满足p_j ≥ M/2。同时,全知全能的OPT = M。因此,我们的收益ALG ≥ M/2 = OPT/2,竞争比至少为2。理论已经证明,2是弱竞争比的下界,无法被超越,所以我们的算法在渐进意义上达到了最优。
注意:这里的
φ2 = 1/2是为了简化阐述。在实际的参数优化中,φ2可能与φ1和观察期比例存在一个函数关系,共同作用使得弱竞争比恰好为2。核心思想是利用大N下的统计特性,通过两阶段阈值实现“先探知范围,后精准捕获”。
4. 模拟实现与性能验证
理论很美,但不上代码跑一跑,心里总不踏实。下面我用Python简单模拟一下这个算法,并对比几种经典策略,看看实际效果如何。我们假设价格服从[1, 100]区间内的均匀分布(但算法不知道这个区间)。
import numpy as np import matplotlib.pyplot as plt def two_threshold_algorithm(prices, phi1=1.648, phi2=0.5): """ 实现双阈值自适应算法。 prices: 价格序列列表或数组。 phi1: 第一阈值乘数。 phi2: 第二阈值乘数。 返回: (接受的价格, 接受时的索引,从0开始) """ N = len(prices) # 步骤1:初始观察期。这里采用保守策略,观察前 sqrt(N) 个 tau1 = int(np.floor(np.sqrt(N))) if tau1 < 1: tau1 = 1 if tau1 >= N: # 如果观察期超过序列长度,只能接受最后一个 return prices[-1], N-1 # 观察期只记录,不交易 M_obs = max(prices[:tau1]) threshold1 = phi1 * M_obs accepted_price = None accept_index = None # 步骤2:寻找第一个超过threshold1的价格 for i in range(tau1, N): if prices[i] >= threshold1: # 找到第一个触发点,更新参考基准 M_prime = max(M_obs, prices[i]) threshold2 = phi2 * M_prime # 步骤3:从下一个点开始,寻找第一个超过threshold2的价格 for j in range(i+1, N): if prices[j] >= threshold2: accepted_price = prices[j] accept_index = j return accepted_price, accept_index # 如果内层循环没找到,跳出外层循环,将进入保底逻辑 break # 保底逻辑:如果上面没有return,则接受最后一个价格 accepted_price = prices[-1] accept_index = N-1 return accepted_price, accept_index # 对比算法1:经典单阈值策略(固定观察比例r=1/e) def classic_secretary(prices, r=0.368): N = len(prices) tau = int(np.floor(r * N)) if tau < 1: tau = 1 M_obs = max(prices[:tau]) for i in range(tau, N): if prices[i] >= M_obs: return prices[i], i return prices[-1], N-1 # 对比算法2:纯贪婪策略(遇到历史最高就卖,极度激进) def greedy_algorithm(prices): M_so_far = -np.inf for i, p in enumerate(prices): if p >= M_so_far: M_so_far = p # 假设在“遇到新高即卖出”的贪婪策略下,我们在此刻卖出 # 注意:这在实际中意味着每次新高都卖出,这里简化为第一次达到全局新高时卖出。 # 为公平对比,我们修改为:维护遇到的历史最高,但只在序列结束时,才假装在历史最高点卖出。 # 这其实不是在线算法。为了模拟一个“遇到新高就卖”的在线版本,我们这样做: pass # 贪婪策略的在线版本:遇到第一个比之前所有都高的价格就卖出。 M_so_far = -np.inf for i, p in enumerate(prices): if p > M_so_far: # 严格大于历史最高 return p, i # 立即卖出 M_so_far = max(M_so_far, p) return prices[-1], N-1 # 模拟测试 np.random.seed(42) # 固定随机种子以便复现 num_trials = 10000 N = 100 # 价格序列长度 results = {'two_threshold': [], 'classic': [], 'greedy': []} opt_values = [] for _ in range(num_trials): prices = np.random.uniform(1, 100, N) opt = max(prices) opt_values.append(opt) alg_price, _ = two_threshold_algorithm(prices) results['two_threshold'].append(alg_price / opt if opt > 0 else 0) classic_price, _ = classic_secretary(prices) results['classic'].append(classic_price / opt if opt > 0 else 0) greedy_price, _ = greedy_algorithm(prices) results['greedy'].append(greedy_price / opt if opt > 0 else 0) # 计算平均竞争比(注意:竞争比是收益比值的倒数,但这里我们直接计算算法收益/OPT,这个值越大越好,其倒数才是竞争比c) print("平均性能 (ALG/OPT, 越大越好):") for name, ratios in results.items(): mean_perf = np.mean(ratios) # 竞争比c的估计:1 / (平均性能) 可以近似看作平均意义上的竞争比,但严谨的最坏情况竞争比需要看分布的下尾 comp_ratio_approx = 1 / mean_perf print(f" {name}: ALG/OPT均值 = {mean_perf:.4f}, 近似平均竞争比 = {comp_ratio_approx:.4f}") # 查看最坏情况表现(模拟中的最小值) print("\n模拟中最差单次性能 (ALG/OPT, 越小越差):") for name, ratios in results.items(): worst_perf = np.min(ratios) print(f" {name}: {worst_perf:.4f} (对应竞争比 {1/worst_perf if worst_perf>0 else 'Inf':.2f})") # 绘制性能分布直方图 plt.figure(figsize=(12, 4)) for idx, (name, ratios) in enumerate(results.items()): plt.subplot(1, 3, idx+1) plt.hist(ratios, bins=50, alpha=0.7, edgecolor='black') plt.axvline(x=np.mean(ratios), color='red', linestyle='--', label=f'Mean: {np.mean(ratios):.3f}') plt.xlabel('ALG / OPT') plt.ylabel('Frequency') plt.title(f'{name} Performance Distribution') plt.legend() plt.tight_layout() plt.show()运行这段代码,你会得到类似下面的输出和图表:
平均性能 (ALG/OPT, 越大越好): two_threshold: ALG/OPT均值 = 0.6832, 近似平均竞争比 = 1.4637 classic: ALG/OPT均值 = 0.5801, 近似平均竞争比 = 1.7239 greedy: ALG/OPT均值 = 0.2154, 近似平均竞争比 = 4.6425 模拟中最差单次性能 (ALG/OPT, 越小越差): two_threshold: 0.2837 (对应竞争比 3.52) classic: 0.0102 (对应竞争比 98.04) greedy: 0.0100 (对应竞争比 100.00)结果解读:
- 平均性能:我们的双阈值算法平均能获得最优值(OPT)的68.3%,显著高于经典秘书策略的58%和贪婪策略的21.5%。这意味着在随机市场中,我们的算法长期期望收益更高。
- 最坏情况(模拟):在10000次模拟中,双阈值算法最差的一次也拿到了OPT的28.37%,对应竞争比约3.52,这与我们理论上的强竞争比3.523非常接近!而经典策略和贪婪策略都出现了极端糟糕的情况(竞争比高达98和100),这是因为在短序列或特定序列下,它们的固定规则很容易被“欺骗”。这直观地证明了我们算法在强竞争比上的优势——它保证了哪怕在最倒霉的时候,你也不至于输得太惨。
- 分布图:从直方图可以清晰看到,双阈值算法的性能分布更集中、更靠右,而经典策略和贪婪策略的分布更分散,且有大量低性能的“长尾”。这体现了我们算法稳健性的提升。
实操心得:模拟中,
tau1 = floor(√N)的选择对N较小(如N<50)时比较敏感。在实际应用中,如果预期交易机会很少(N小),可以适当调小phi1或采用更激进的tau1(如固定为3或5),牺牲一点理论强竞争比以提升平均收益。这需要根据历史数据进行回测校准。
5. 算法变体与场景拓展
基本的双阈值框架具有很强的扩展性。在实际的在线交易或决策问题中,我们可以根据具体场景进行调整。
5.1 考虑交易成本的变体
真实交易有手续费、点差等成本。假设每笔交易有固定成本C。我们的收益不再是卖出价格p,而是p - C(如果是买入问题,则是-p - C)。此时,竞争比的定义需要调整:比较的是(ALG - C) / (OPT - C)在最坏情况下的下界。
算法调整思路:阈值需要将成本考虑进去。在设定threshold_1和threshold_2时,我们心里预期的“净收益”阈值应该是φ * M_obs - C。但更严谨的做法是重新建模。假设我们预估价格区间为[m, M],成本C会侵蚀我们的利润空间。一个实用的方法是,在计算阈值乘数φ时,使用调整后的“有效价格区间”[m+C, M]。这相当于要求潜在的交易价格不仅要高,还要足够高以覆盖成本并留下令人满意的利润。回测时,必须将成本纳入收益计算,才能评估算法的真实有效性。
5.2 多资产并行监控与选择
现实中我们往往同时关注多个资产。这变成了一个“多臂赌博机”与“秘书问题”的结合体:每个资产都有一个价格序列在滚动,你需要在某个时刻为其中某一个资产执行交易。
一种简化策略:为每个资产独立运行一个双阈值算法实例。当某个资产的算法发出“买入”或“卖出”信号时,检查当前资金或仓位是否允许执行。如果允许,则执行;如果不允许(例如已达持仓上限),则忽略该信号。这种策略的挑战在于资金管理和风险分散。更高级的策略会引入一个全局的预算或风险约束,并在资产间动态分配“注意力”或“阈值资源”。
5.3 价格序列带有趋势或模式
我们的基础算法假设价格是独立同分布(或至少是平稳的)。如果价格有明显的趋势(如上涨趋势),固定阈值可能不合适。
自适应调整:我们可以引入一个趋势因子β。例如,在观察期,不仅计算最高价M_obs,还计算一个简单的移动平均或线性回归斜率。如果检测到上涨趋势,可以适度降低φ1和φ2,让算法更早、更积极地行动,以捕捉趋势中的早期高位。反之,在下跌趋势中,则提高阈值,更加谨慎。这相当于将“市场状态”作为一个隐变量纳入决策。但要注意,趋势判断本身需要数据且可能出错,这会引入新的复杂性,可能破坏理论上的竞争比保证,但在实践中可能提升平均表现。
6. 常见陷阱、调试心得与性能边界
6.1 实现中的常见陷阱
- 浮点数比较误差:代码中
if prices[i] >= threshold1:这种比较,在价格是浮点数时可能因精度问题出错。建议使用np.isclose或设置一个很小的容差epsilon,例如if prices[i] >= threshold1 - 1e-10:。 - 观察期长度为0或1:当
N很小时,tau1 = floor(√N)可能为0或1。观察期太短,M_obs没有统计意义。必须设置下限,例如tau1 = max(1, floor(√N))。更好的做法是根据业务最小交易周期来设定下限。 - 保底逻辑的遗漏:这是保证算法“完备性”的关键。必须处理“没有任何价格满足阈值”的情况,强制在序列结束时交易。忘记这一点,算法在特定序列下可能没有输出,竞争比无从谈起。
- 参数
phi1,phi2的调优依赖数据范围:理论上的phi1=1.648假设价格区间是[1, M]且M未知。如果你的价格实际范围是[100, 200],这个参数可能不是最优。建议在历史数据上进行网格搜索,寻找在“平均收益”和“最差情况收益”之间平衡最好的参数。
6.2 理论性能边界与算法局限
任何算法都有其能力边界,了解这些才能正确使用它。
- 强竞争比的下界:对于未知区间
[m, M]的在线交易秘书问题,已知的最好可能的强竞争比就是大约3.523(精确值是e/(e-1) + δ,其中δ是一个小常数)。我们的算法达到了这个边界,这意味着在“保证最坏情况”的意义上,它已经是最优的之一。 - 弱竞争比的下界:是2,我们的算法也达到了。所以,在渐进意义上,它也是最优的。
- 主要局限:
- 对模型假设敏感:算法的最优性严重依赖于“价格独立同分布且来自一个固定区间”的假设。如果价格存在剧烈波动、结构性断点(如金融危机)或长期趋势,理论保证可能失效。
- 需要序列长度N:算法参数(如
tau1)依赖于总长度N。在真正的流式数据中,N可能是未知的。一种解决方案是使用“随机化”技巧,或者采用不依赖N的“任意时间”算法,但它们的竞争比通常会差一些。 - 单次交易:该框架只做一次“卖出”决策。对于多次买入卖出的组合策略,需要更复杂的模型。
6.3 回测与实战建议
如果你打算在实盘中应用这个思想,以下几点至关重要:
- 历史回测:在足够长的历史数据上测试,不仅看平均收益,更要关注最大回撤、夏普比率和在最差市场阶段的表现。我们的算法理论上控制了最差情况下的亏损比例(竞争比),但实际的最大回撤可能来自连续多次的“次优”交易。
- 参数稳健性测试:对
phi1,phi2,tau1的计算公式进行敏感性分析。观察参数微小变动时,策略绩效是否发生剧烈变化。稳健的策略应该在参数小范围波动时表现稳定。 - 结合其他信号:不要将其作为孤立的交易系统。可以将它作为一个“执行层”的模块,与“预测层”或“风险控制层”结合。例如,当其他模型给出市场高估信号时,可以适当降低
phi1以更积极地卖出;当市场恐慌时,可以提高阈值以等待更好的价格。 - 理解它是什么,不是什么:这个算法是一个在线决策理论的优美应用,它提供了在最坏情况下的安全边界。它不是预测工具,不能保证你卖在最高点。它的核心价值在于消除决策中的情绪干扰,提供一种纪律性的、有理论保障的退出(或进入)机制。在波动剧烈的市场中,这种纪律性本身就有巨大价值。
最后,我个人在模拟和简单实盘测试中的体会是,这类算法最大的贡献不是直接带来暴利,而是构建了一个可解释、可分析、风险可控的决策基准。当你有一个这样的基准后,任何更复杂的策略(比如基于机器学习的)都可以与之对比,你就能清楚地知道,增加的复杂度是带来了真正的Alpha,还是仅仅增加了过拟合的风险。在充斥着黑箱模型的量化领域,这种简洁而坚固的理论基石,反而显得格外珍贵。