BriefGPT - AI 论文速递
·
具有未知延迟的在线顺序决策
💡
原文中文，约400字，阅读约需1分钟。
📝
内容提要
本文介绍了在线多梯度下降算法（OMGD）在有限信息环境下的应用，OMGD算法在二次切换成本问题中具有竞争比为至多4(L+5)+(16(L+5))/μ的性能。对于有界信息环境中的在线算法，其竞争比的上界和下界分别为max{Ω(L), Ω(L/√μ)}。此外，OMGD算法实现了有限信息环境下的动态最优遗憾，对于线性切换成本，其竞争比的上界取决于问题实例的路径长度、平方路径长度以及L、μ。因此，在有限信息环境中，二次和线性切换成本的最优竞争比是不同的。
🎯
关键要点
- 本文介绍了在线多梯度下降算法（OMGD）在有限信息环境下的应用。
- OMGD算法在二次切换成本问题中的竞争比为至多4(L+5)+(16(L+5))/μ。
- 有界信息环境中的在线算法竞争比的上界和下界分别为max{Ω(L), Ω(L/√μ)}。
- OMGD算法实现了有限信息环境下的动态最优遗憾。
- 对于线性切换成本，OMGD算法的竞争比上界取决于路径长度、平方路径长度以及L、μ。
- 在有限信息环境中，二次和线性切换成本的最优竞争比是不同的。
➡️
