譯者 | 崔皓

審校 | 孫淑娟

研究人員提出了一些方法，在理論上保證重尾獎(jiǎng)勵(lì)分布的先驗(yàn)信息最小的情況下?lián)p失最小。

研究多臂賭博機(jī)問(wèn)題（MABs）是為了解決不確定環(huán)境下的連續(xù)決策問(wèn)題，針對(duì)多臂賭博機(jī)（MABs）的探索算法通常假定獎(jiǎng)勵(lì)噪聲為輕尾分布。然而，現(xiàn)實(shí)世界的數(shù)據(jù)集往往是重尾噪聲的。有鑒于此，來(lái)自韓國(guó)的研究人員提出了一種算法，該算法能夠以最小的先驗(yàn)信息實(shí)現(xiàn)最小的最優(yōu)性（最大損失情況下的最小損失）。與現(xiàn)有算法相比，新算法在自主交易和個(gè)性化推薦系統(tǒng)中具有潛在的應(yīng)用。

在數(shù)據(jù)科學(xué)中，研究人員通常要處理包含噪聲的觀測(cè)數(shù)據(jù)。在這種情況下，數(shù)據(jù)科學(xué)家探索順序決策的問(wèn)題。也被稱為 "隨機(jī)多臂賭博機(jī)"問(wèn)題（stochastic MAB）。在這里，一個(gè)智能代理在一個(gè)不確定的環(huán)境下，根據(jù)嘈雜的獎(jiǎng)勵(lì)（Rewards），依次探索和選擇行動(dòng)。它的目標(biāo)是最小化累積遺憾（Regret）--最大獎(jiǎng)勵(lì)（Rewards）和所選行動(dòng)的預(yù)期獎(jiǎng)勵(lì)之間的差異。遺憾（Regret）越小，意味著決策效率越高。

大多數(shù)現(xiàn)有的關(guān)于隨機(jī)MABs的研究都是在獎(jiǎng)勵(lì)噪聲遵循輕尾分布的假設(shè)下進(jìn)行遺憾分析。然而，事實(shí)上，許多現(xiàn)實(shí)世界的數(shù)據(jù)集顯示出重尾的噪聲分布。這些數(shù)據(jù)包括用于開(kāi)發(fā)個(gè)性化推薦系統(tǒng)的用戶行為模式數(shù)據(jù)，用于自動(dòng)交易開(kāi)發(fā)的股票價(jià)格數(shù)據(jù)，以及用于自動(dòng)駕駛的傳感器數(shù)據(jù)。

在最近的一項(xiàng)研究中，韓國(guó)中央大學(xué)的Kyungjae Lee助理教授和蔚山科技學(xué)院的Sungbin Lim助理教授都解決了這個(gè)問(wèn)題。在他們的理論分析中，他們證明了現(xiàn)有的隨機(jī)MABs算法對(duì)于重尾獎(jiǎng)勵(lì)是次優(yōu)的。更具體地說(shuō)，這些算法采用的方法--穩(wěn)健的置信度上限（UCB）和具有無(wú)界擾動(dòng)的自適應(yīng)擾動(dòng)探索（APE）--不能保證最小化（最大可能損失的最小化）的最優(yōu)性。

"基于這一分析，提出了最小最優(yōu)魯棒（MR）UCB和APE方法。MR-UCB利用更嚴(yán)格的穩(wěn)健均值估計(jì)器的置信度約束，而MR-APE是其隨機(jī)化版本。它采用了有界擾動(dòng)，其規(guī)模與MR-UCB中修改后的置信度界限一致，"李博士在談到他們的工作時(shí)解釋說(shuō)，這項(xiàng)工作于2022年9月14日發(fā)表在IEEE神經(jīng)網(wǎng)絡(luò)與學(xué)習(xí)系統(tǒng)期刊上。

研究人員接下來(lái)得出了依賴差距和獨(dú)立的累積遺憾的上界。對(duì)于這兩種提議的方法，后者的值與重尾噪聲假設(shè)下的下限相吻合，從而實(shí)現(xiàn)了最小的最優(yōu)性。此外，新方法需要最小的先驗(yàn)信息，并且只依賴于獎(jiǎng)勵(lì)有界時(shí)刻的最大順序。相比之下，現(xiàn)有的算法需要該時(shí)刻的上限，而這一先驗(yàn)信息在許多現(xiàn)實(shí)世界的問(wèn)題中可能無(wú)法獲得。

在建立了他們的理論框架后，研究人員通過(guò)在帕累托和弗雷謝噪聲下進(jìn)行模擬測(cè)試了他們的方法。他們發(fā)現(xiàn)，MR-UCB的表現(xiàn)一直優(yōu)于其他探索方法，而且在重尾噪聲下，隨著行動(dòng)數(shù)量的增加，MR-UCB更加穩(wěn)健。

此外，兩人利用加密貨幣數(shù)據(jù)集驗(yàn)證了他們的方法，表明MR-UCB和MR-APE在處理重尾的合成和現(xiàn)實(shí)世界的隨機(jī)MAB問(wèn)題上是有益的--最大的最佳遺憾界限和最小的先驗(yàn)知識(shí)。

由于容易受到重尾噪聲的影響，現(xiàn)有的MAB算法在對(duì)股票數(shù)據(jù)進(jìn)行建模時(shí)表現(xiàn)不佳。他們無(wú)法預(yù)測(cè)股票價(jià)格的大幅上漲或突然下跌，造成巨大的損失。相比之下，MR-APE可用于自主交易系統(tǒng)，通過(guò)股票投資獲得穩(wěn)定的預(yù)期收益，"李博士在討論本項(xiàng)工作的潛在應(yīng)用時(shí)評(píng)論道。"此外，它還可以應(yīng)用于個(gè)性化的推薦系統(tǒng)，因?yàn)樾袨閿?shù)據(jù)顯示出重尾的噪音。有了對(duì)個(gè)人行為的更好預(yù)測(cè)，就有可能提供比傳統(tǒng)方法更好的推薦，這可以使廣告收入最大化，"他總結(jié)道。

譯者介紹

崔皓，51CTO社區(qū)編輯，資深架構(gòu)師，擁有18年的軟件開(kāi)發(fā)和架構(gòu)經(jīng)驗(yàn)，10年分布式架構(gòu)經(jīng)驗(yàn)。曾任惠普技術(shù)專家。樂(lè)于分享，撰寫了很多熱門技術(shù)文章，閱讀量超過(guò)60萬(wàn)。《分布式架構(gòu)原理與實(shí)踐》作者。?

原文標(biāo)題：??Chung-Ang University Researchers Develop Algorithm for Optimal Decision Making under Heavy-tailed Noisy Rewards??