在线算法模型

在线困难来自动作发生时未来仍被信息屏障挡住，并不要求算法记忆有限。一个决定若能等到完整输入再作或可免费撤回，就能退化成离线优化；若撤回要付迁移费，这笔费用必须进入状态和成本，而不是当作事后修正。

边界 ​

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 的竞争比。协议相似，评价对象不同。