Bandit 004|如何使用鞅集中不等式分析強盜演算法?

閱讀時間約 1 分鐘

今天繼續聊聊由Yasin Abbasi-Yadkori [1] 於2011年發表的文章,


《Improved Algorithms for Linear Stochastic Bandits》[2]。


今天主要想討論在第11頁的Lemma 8,


Yasin 展示了如何構造「超鞅 Supermartingale」,


來進一步使用「鞅集中不等式 Martingale Concentration Inequality」做分析。


直觀看,行動特徵向量是d維度的,而鞅原則上都是1維度的,


兩者如何能結合呢?


這一定有某個地方,把行動特徵向量做了降維度。


而沒錯,這裡也做了降維度。


Lemma 8 主要介紹一個參數向量 lambda,


跟特徵向量做內積,於是就變成1維了。


而更有趣的技巧在,


文章第4頁定義了 Sgima-代數,


是有包含行動特徵向量的,


所以並不需要考慮行動特徵向量的分佈,


因為在給定的「過濾 Filtration」下,


行動特徵向量並沒有隨機性。


如此,隨機性就完全來自源頭假設獎勵模型裡面的噪音。


Yasin這篇文章中,假設的分佈是 R-次高斯,


所以可以先透過一些高斯分佈相關的Calculus,


來了解給這個噪音乘以常數除以常數後的分佈。


於是,就從原本R-次高斯分佈的定義,


推導出了「鞅差 Martingale Difference」的定義,


進一步構造了「超鞅 Supermartingale」。


Bandit算法裡面各種對任何時刻都對的機率不等式,


基本上都有「超鞅 Supermartingale」在裡面。


Reference

[1] https://scholar.google.com/citations?user=0WsQ0uUAAAAJ&hl=da

[2] https://arxiv.org/abs/1611.06534




366會員
1.1K內容數
Outline as Content
留言0
查看全部
發表第一個留言支持創作者!
王啟樺的沙龍 的其他內容
1. 過度堅持自己的審美觀念: - 當你堅持只從個人審美角度評價事物,可能會忽略其他重要的學術或實際標準。例如,您可能認為某個研究方法不夠「美」而拒絕採用,這可能導致錯失更好的研究成果。同樣地,在選擇研究課題時,如果過於偏重自己的興趣而忽視了其實際應用價值,可能會影響你在學術界的影響力和發展。
寫短文是為了與有趣的想法邂逅,然後把有趣的想法在自己的腦中過一過。 讀書讀到一段有意思,如果沒有寫作,那留下的印象少, 其實跟沒讀書一樣。 而避免這樣徒勞無功的秘訣,就是利用山口拓郎說的,要將自己的意見「具體化」。
看著網路教學使用卡片盒筆記法的碩博士生,都會踩到的3個陷阱: 1. 依賴誤導性的資料來源: 2. 缺乏實際寫作經驗: 3. 沒有文化背景支撐: 你在使用卡片盒筆記法的過程中還見過什麼其他錯誤?
我目前在Obsidian的實踐上,我有三種主要的連結策略: 01 用筆記標題去連結有結構的從屬關係 02 用參考資料連結筆記庫外的補充資料 03 用Obsidian內部連結[4]筆記庫內的補充資料
1. 盲目自信: - 剛開始做實驗時,博士生常常會有一種「我的實驗設計一定有道理」的心態。這種心態讓他們在未得到預期結果時,會認為只是某個設定出了問題,只要加班加點,各種嘗試,一定可以突破。實際上,這種盲目的自信會導致博士生在錯誤的方向上浪費大量時間和精力,最終結果可能並不理想。 2.
「啟發筆記」由「摘錄」+「 自由寫作 」兩個部分構成。 「摘錄」的部分是指你閱讀的「文章」「書本」上的原汁原味內容, 你需要將原文一字不漏照抄,以避免斷章取義或者轉述上出現落差。 而「自由寫作」則是你做完「摘錄」後, 馬上紀錄自己心中的想法, 抓住自己各種念頭, 用寫作讓他們現形成文字,
1. 過度堅持自己的審美觀念: - 當你堅持只從個人審美角度評價事物,可能會忽略其他重要的學術或實際標準。例如,您可能認為某個研究方法不夠「美」而拒絕採用,這可能導致錯失更好的研究成果。同樣地,在選擇研究課題時,如果過於偏重自己的興趣而忽視了其實際應用價值,可能會影響你在學術界的影響力和發展。
寫短文是為了與有趣的想法邂逅,然後把有趣的想法在自己的腦中過一過。 讀書讀到一段有意思,如果沒有寫作,那留下的印象少, 其實跟沒讀書一樣。 而避免這樣徒勞無功的秘訣,就是利用山口拓郎說的,要將自己的意見「具體化」。
看著網路教學使用卡片盒筆記法的碩博士生,都會踩到的3個陷阱: 1. 依賴誤導性的資料來源: 2. 缺乏實際寫作經驗: 3. 沒有文化背景支撐: 你在使用卡片盒筆記法的過程中還見過什麼其他錯誤?
我目前在Obsidian的實踐上,我有三種主要的連結策略: 01 用筆記標題去連結有結構的從屬關係 02 用參考資料連結筆記庫外的補充資料 03 用Obsidian內部連結[4]筆記庫內的補充資料
1. 盲目自信: - 剛開始做實驗時,博士生常常會有一種「我的實驗設計一定有道理」的心態。這種心態讓他們在未得到預期結果時,會認為只是某個設定出了問題,只要加班加點,各種嘗試,一定可以突破。實際上,這種盲目的自信會導致博士生在錯誤的方向上浪費大量時間和精力,最終結果可能並不理想。 2.
「啟發筆記」由「摘錄」+「 自由寫作 」兩個部分構成。 「摘錄」的部分是指你閱讀的「文章」「書本」上的原汁原味內容, 你需要將原文一字不漏照抄,以避免斷章取義或者轉述上出現落差。 而「自由寫作」則是你做完「摘錄」後, 馬上紀錄自己心中的想法, 抓住自己各種念頭, 用寫作讓他們現形成文字,
你可能也想看
Thumbnail
八十-二十法則提到,在多數生活的現象中,約80%的效果是來自於20%的原因,除了經濟學、學習理論外,這個法則同樣也可以應用在生活中的幸福感上。 我們需要認知到擁有的越多不一定會越快樂,反而有可能會因為無法專注在少數事物上而產生空虛、迷茫的感覺。「極簡」精神最重要的一點在於放下對於「多」的執著,將有
Thumbnail
1.加權指數與櫃買指數 週五的加權指數在非農就業數據開出來後,雖稍微低於預期,但指數仍向上噴出,在美股開盤後於21500形成一個爆量假突破後急轉直下,就一路收至最低。 台股方面走勢需觀察週一在斷頭潮出現後,週二或週三開始有無買單進場支撐,在沒有明確的反轉訊號形成前,小夥伴盡量不要貿然抄底,或是追空
Thumbnail
近期的「貼文發佈流程 & 版型大更新」功能大家使用了嗎? 新版式整體視覺上「更加凸顯圖片」,為了搭配這次的更新,我們推出首次貼文策展 ❤️ 使用貼文功能並完成這次的指定任務,還有機會獲得富士即可拍,讓你的美好回憶都可以用即可拍珍藏!
Thumbnail
OpenAI近日在發佈會上發表了他們創造的最新AI「GPT-4o」。本文將介紹GPT-4o如何使用、功能以及發表會資訊。
Thumbnail
接觸新的保養品時,如何使用、何時使用以及需要注意的事項都非常重要。 瞭解如何正確使用伊絲碧媞的保養品對於美麗的回報至關重要。 本手冊已詳細記載使用者可能遇到的各種疑問,並提供專業美容老師的諮詢,讓您能確保對產品的使用有所感受。
Thumbnail
可以用 #revit 放辦公室OA桌椅套件,然後 桌椅套件 #明細表,新增欄位 ex [中午吃甚麼]、 [下午茶喝什麼] ,填好按 #同步(跟#Google #excel 一樣,只是手動同步),這樣子大家就都會 #協同 啦~ A0-1、A0-2 #圖紙 放 #午餐、#下午茶 #菜單。A0-0
Thumbnail
在當代數據驅動的設計領域裡,了解用戶如何與你的網站互動是至關重要的。Microsoft Clarity是一款功能強大的用戶分析工具,它提供的直觀見解可以幫助開發者和設計師深入掌握用戶行為,從而優化用戶體驗和提升網站性能。
Relx通用彈/煙彈會比吸煙好嗎? Relx的煙彈不是完全無害的,但它的危害性比傳統香煙小得多。為了打破不良的吸煙習慣,Relx可以是另一吸煙替代品選擇。如果是慣性吸煙者,改用Relx電子煙是一個不錯的選擇。但如果從不吸煙,開始前最好考慮清楚。 多少口的Relx電子煙等於一包香煙?
Thumbnail
對於數位創作者來說,生財工具不外乎是電腦、手機、平板...等設備,對於生財工具一定會相當重視,也會希望生財工具能穩定發揮一定的效能。 使用電腦的時候,最害怕電腦突然罷工,我曾經遇過電腦突然打不開,或是使用電腦的時候,電腦就突然關機,然後電腦再也開不起來,遇到這些狀況,當下真的很無力...。
Thumbnail
Hi there,上個月中 Clean Bandit 和瑞典歌手 A7S 合作,推出了全新單曲〈Everything But You〉(2022),這兩組能夠想見音樂風格的音樂人,合作後卻發展出了很不一樣的音樂火花,至少跟我原先想像的有點落差😅。已負盛名的 Clean Bandit 我想
Thumbnail
    Hi there,不知道大家有沒有發現,Whitney Houston 在1985年發行的〈How Will I Know〉,最近被英國電音樂團 Clean Bandit 拿來重新製作,聽過的人應該會覺得超級不一樣的吧。原先發行的〈How Will I Know〉收錄在 Whitney 的
Thumbnail
八十-二十法則提到,在多數生活的現象中,約80%的效果是來自於20%的原因,除了經濟學、學習理論外,這個法則同樣也可以應用在生活中的幸福感上。 我們需要認知到擁有的越多不一定會越快樂,反而有可能會因為無法專注在少數事物上而產生空虛、迷茫的感覺。「極簡」精神最重要的一點在於放下對於「多」的執著,將有
Thumbnail
1.加權指數與櫃買指數 週五的加權指數在非農就業數據開出來後,雖稍微低於預期,但指數仍向上噴出,在美股開盤後於21500形成一個爆量假突破後急轉直下,就一路收至最低。 台股方面走勢需觀察週一在斷頭潮出現後,週二或週三開始有無買單進場支撐,在沒有明確的反轉訊號形成前,小夥伴盡量不要貿然抄底,或是追空
Thumbnail
近期的「貼文發佈流程 & 版型大更新」功能大家使用了嗎? 新版式整體視覺上「更加凸顯圖片」,為了搭配這次的更新,我們推出首次貼文策展 ❤️ 使用貼文功能並完成這次的指定任務,還有機會獲得富士即可拍,讓你的美好回憶都可以用即可拍珍藏!
Thumbnail
OpenAI近日在發佈會上發表了他們創造的最新AI「GPT-4o」。本文將介紹GPT-4o如何使用、功能以及發表會資訊。
Thumbnail
接觸新的保養品時,如何使用、何時使用以及需要注意的事項都非常重要。 瞭解如何正確使用伊絲碧媞的保養品對於美麗的回報至關重要。 本手冊已詳細記載使用者可能遇到的各種疑問,並提供專業美容老師的諮詢,讓您能確保對產品的使用有所感受。
Thumbnail
可以用 #revit 放辦公室OA桌椅套件,然後 桌椅套件 #明細表,新增欄位 ex [中午吃甚麼]、 [下午茶喝什麼] ,填好按 #同步(跟#Google #excel 一樣,只是手動同步),這樣子大家就都會 #協同 啦~ A0-1、A0-2 #圖紙 放 #午餐、#下午茶 #菜單。A0-0
Thumbnail
在當代數據驅動的設計領域裡,了解用戶如何與你的網站互動是至關重要的。Microsoft Clarity是一款功能強大的用戶分析工具,它提供的直觀見解可以幫助開發者和設計師深入掌握用戶行為,從而優化用戶體驗和提升網站性能。
Relx通用彈/煙彈會比吸煙好嗎? Relx的煙彈不是完全無害的,但它的危害性比傳統香煙小得多。為了打破不良的吸煙習慣,Relx可以是另一吸煙替代品選擇。如果是慣性吸煙者,改用Relx電子煙是一個不錯的選擇。但如果從不吸煙,開始前最好考慮清楚。 多少口的Relx電子煙等於一包香煙?
Thumbnail
對於數位創作者來說,生財工具不外乎是電腦、手機、平板...等設備,對於生財工具一定會相當重視,也會希望生財工具能穩定發揮一定的效能。 使用電腦的時候,最害怕電腦突然罷工,我曾經遇過電腦突然打不開,或是使用電腦的時候,電腦就突然關機,然後電腦再也開不起來,遇到這些狀況,當下真的很無力...。
Thumbnail
Hi there,上個月中 Clean Bandit 和瑞典歌手 A7S 合作,推出了全新單曲〈Everything But You〉(2022),這兩組能夠想見音樂風格的音樂人,合作後卻發展出了很不一樣的音樂火花,至少跟我原先想像的有點落差😅。已負盛名的 Clean Bandit 我想
Thumbnail
    Hi there,不知道大家有沒有發現,Whitney Houston 在1985年發行的〈How Will I Know〉,最近被英國電音樂團 Clean Bandit 拿來重新製作,聽過的人應該會覺得超級不一樣的吧。原先發行的〈How Will I Know〉收錄在 Whitney 的