在线算法模型

协议 ​

请求 ${\sigma }_t$ 到达后，算法仅依据历史和当前请求选动作 $a_t$ 并付成本；离线 OPT 预知整段 $\sigma$。确定算法无内部随机性，随机算法的期望须说明对算法硬币取，并区分 oblivious 与 adaptive 对手。

Paging 中页面请求到达，缺页时必须立即淘汰；知道未来的 Belady 策略属于离线。在线并不等于流式：前者限制未来信息并要求决策，后者主要限制空间，可能不输出动作。

边界 ​

Worst-case 序列不等于能看见本轮随机位的 adaptive 对手。Advice 模型额外获得未来编码，也应单列。动作若可事后免费撤回，原在线困难可能消失。

评价可用竞争比、regret 或其他目标；本批以竞争分析公理库竞争分析Competitive analysis在同一请求序列上比较在线算法总成本与预知未来的离线最优。为主，不把学习比较器自动带入。

不可撤回也可以表现为撤回需付迁移或取消成本。若允许免费等待全部输入后再修改动作，问题就退化为离线优化；具体动作时间必须写进协议。

信息过滤与动作时间 ​

在第 $t$ 轮，算法可见历史 $H_{t-1}$ 与当前请求 ${\sigma }_t$，输出 $a_t=A(H_{t-1},{\sigma }_t;r)$，然后成本和反馈进入 $H_t$。未来请求不在可见信息中。Paging 的淘汰发生在 fault 当下；ski rental 的购买在知道当天仍需使用后、未知明天前决定。

若动作可以延后到看完整序列，paging 可运行 Belady、ski rental 可直接取 $min(T,B)$，在线困难消失。若撤销动作需迁移费，则迁移本身是成本而非免费修正。

对手与随机性 ​

Oblivious 对手先固定序列，再对算法随机性取期望；adaptive online 对手可依据过去动作发下一请求，但不能在本轮随机动作实现后倒改当前请求。若对手能见完整种子，随机算法常退化到确定性下界。

Advice 模型额外给若干未来信息 bits，prediction-augmented 模型给可能错误预测；它们必须同时报告一致性和鲁棒性，不能沿用无 advice 的竞争比而不改基准。

与 streaming 和 online learning 的分界 ​

Streaming 可能只在末尾输出、核心资源是空间；online algorithm 核心是不可撤回决策，可保存全部历史。Online learning 常用 regret 与固定比较器，经典在线算法用离线 OPT 的竞争比。协议相似，评价对象不同。

参考资料

• Borodin, El-Yaniv, Online Computation and Competitive Analysis, 1998.
• Sleator, Tarjan, CACM 1985.