在线算法模型

把未来遮住以后，同一个前缀可能接上要求相反决策的后缀。在线算法必须先选一个动作，之后才知道另一个动作是否更好。已付租金、已发生的缺页或迁移费用无法靠事后更改答案抹去，这正是信息不足产生代价的地方。

图中的信息边界随请求向前移动。算法可以记住边界左侧的全部历史，仍然是在线算法；若获准等到边界走完整个输入才决定，原来的问题就变了。

相同前缀怎样制造两难 ​

设买滑雪板需 10 元，租一天需 1 元。第一天开始时，使用一天和使用一百天的两种情形完全相同。立即购买在前一种情形花 10 元，离线只租一天花 1 元；一直租赁在后一种情形花 100 元，离线直接购买花 10 元。阈值策略必须在未来仍未知时决定何时切换，详细成本见Ski Rental 问题理路Ski Rental 问题Ski rental problem在未知使用天数下决定继续按日租用还是一次购买。。

Paging理路Paging 问题Paging problem在容量 k 的缓存中在线服务页面请求，并以缺页次数计成本。也有相同信息结构：缓存已满且请求缺页时，必须选一页淘汰。未来最晚再使用的页面是离线 Belady 策略的选择依据，在线算法此刻并不知道它。若允许撤回淘汰或迁移状态，这些操作的费用与完成时间也必须写进协议。

对手能看见什么 ​

不知随机结果的对手（oblivious adversary）先固定整条请求序列，之后算法才运行。自适应对手可以根据已观察的动作决定下一请求；即使看不见内部种子，它也可能从动作推断部分随机结果。不过，它不能等本轮动作完成后再倒改本轮请求。

在自适应模型下，请求序列本身可能随算法随机位变化，因而不能未经说明直接使用“固定 $\sigma$、只对左边取期望”的公式。还须约定对手怎样服务请求，以及比较器拥有怎样的信息。能够看见完整随机种子的对手更强：它可以针对种子所确定的行为挑选输入。

流式算法（streaming）主要限制存储空间，可能只在输入结束时输出结果；在线算法主要限制决策时的信息，可以保留全部历史。在线学习常把累计损失与某个固定行动的损失相比，称为 regret；这里的离线最优通常可以随整段请求安排一串动作，两种比较器不能互换。

Advice 模型允许算法得到未来信息的编码，预测辅助模型则提供可能出错的未来预测。此时应说明新增信息的长度或误差含义。预测算法常分别报告预测准确时的一致性与预测任意错误时的鲁棒性；无辅助信息的下界不能不加解释地移用于这些新模型。