Algorithm DIY problem explained

一、前言與研究動機

身為一個透過校學士學程來修電機系演算法的財金系學生，一個比較不需要金融先備知識，同時又可以運用演算法課程知識的，應該就是「資產組合配置」了。(其實更有可能顯現出演算法強大力量的是期貨與選擇權的定價，我可能有空時再寫一篇DIY闡述。) 以長期投資的視角來說，我會想要在不同的時間，對選定的資產或資產組合作出正確的買入與賣出的決策，讓我不只在「單期」做出最好的決定，也能夠在長期投資環境的變化，適時選擇不同的資產配置。

我在財金系的專題研究「機器人理財」，我們想要針對不同風險屬性的客戶，打造個人專屬的資產配置組合，讓投資人可以正確且有效率地往他們設定的理財目標邁進，其中，「再平衡」機制，也就是在不同的時間內，幫助客戶重新配置他們的投資組合，是機器人理財專題研究中重要的議題。目前台灣的機器人理財業者雖然有再平衡的機制，但是通常都是靠質化分析居多，以量化分析為輔，因此，我想要設計一套以動態規劃為主的演算法，執行最佳交易策略。

至於為甚麼要選擇用動態規劃解呢? 在課程中，我發先動態規劃是根據目前投資組合的狀態和市場預測，使用動態規劃來找出最佳的再平衡策略和交易順序。雖然使用機器學習來得到最佳投資組合以及不同時間內的資產配置也是一個值得發想的方向，但是這有點超出我的能力範圍，而管理學院常見的迴歸分析模型雖然具有一定的解釋力，但是預測的精確程度不足，R-square值通常都不夠理想。因此，在管院比較不那麼常見的動態規劃問題，或許可以改進我們平常用的回歸模型，來去更好的去廣泛地了解並構建出最佳化的投組，這也是我想要嘗試透過建模並使用演算法動態規劃解決問題的主要原因。

二、問題定義

在多資產的交易決策中，我希望可以在不同的時間點做出不同的交易決定，讓我可以最大化「總收益率」，同時考量到「交易費用」。

在此文中，我定義投資者可以在時間周期 [1, T] 中持有一種給定的資產組合(至於如何選擇那些資產組合來進行計算，這牽扯到現代投資組合理論相關的知識，在此先不展開，可以假設我已經找到數個可能的好標的來進入我考慮的資產池中)，n種資產組合分別為A1, A2, A3…An, 同時他們的收益率分別為 {rA1 1,r A1 2, …,rA1 T}, {rA2 1,rA2 2, …,rA2 T}, …, {rAn 1,rAn 2, …,rAn T}, 收益率可以是歷史的收益率，也可以是透過各式資產定價模型估計的收益率，總之假設這些資產的收益率是已知的。此外，這n種資產組合也包含同樣的一組標的，但是各標的佔資產的權重不同的情況。我們可以用一個T維的組合來表示各期的交易策略：Period(t) = [1 if the investor possesses A1 at t, 2 if the investor possesses A2 at t,…,n if the investor possesses An at t], t = 1,2,…,T。在求解的過程中，我會用S=1,2,3(分別代表三種不同的資產組合A,B,C)來表示。接者，交易費用我假設為總交易額的固定比例α，最後，總收益率我定義為策略在不同期間的收益率總和，也就是 rtotal = ∑T t=1rt 。

三、求解(無交易次數限制)

我之所以會想要用動態規劃的原因，是因為我認為此類型的問題或許可以用遞迴的方式求解。當我遇到這個問題時，我第一時間想到的就是針對不同的投資項目，透過多層的for迴圈來得到未來的最優解，但這就跟在下圍棋時窮盡各式可能性得到最優解一樣不切實際(O(nn))，但我注意到從每個資產項目延伸出的問題都屬於重疊子問題，即出現需要重複解同樣的子問題的情境。這正中動態規劃法的下懷。我們可以針對每個子問題(也就是未來某個狀態的估計報酬率)，並儲存，就有機會大幅降低時間複雜度。

假設Period(t)=s是投資人在[t-1,t]時持有第S種資產，第t期代表t-1時間到t時間，rmax(t, s), t ∈[1-T], s ∈{1,2,3}是在T時間採取S決策時，到時間T為止投資者獲得的最大總收益率。假設在t-1期投資者擁有A，而第t期投資者也是A，那麼在第t期投資者獲得的總收益率是 rmax(t-1, 1)+rA t，如果改成B，則是rmax(t-1, 1)+rB t-α。若投資者在第t-1期持有A，到第t期的總收益率就是：

rcumA(t,s) = rmax(t-1,1)+(S=1)* rA t+(S=2)* rB t+(S=3)* rC t-(S≠1)* α (1)

相對應的，B跟C的情況是：

rcumB(t,s) = rmax(t-1,2)+(S=1)* rA t+(S=2)* rB t+(S=3)* rC t-(S≠2)* α (2)

rcumC(t,s) = rmax(t-1,3)+(S=1)* rA t+(S=2)* rB t+(S=3)* rC t-(S≠3)* α (3)

因此，當時間t採取s決策時，最大收益率就可以表示成

rmax(t,s) = max{rcumA(t,s), rcumB(t,s), rcumC(t,s)} (4)

我們可以假設有一個函數來說明我們這期要選甚麼：

pres(t,s) = {1 if rmax(t,s) = rcumA(t,s), 2 if rmax(t,s) = rcumB(t,s) ,3 if rmax(t,s) = rcumC(t,s)} (5)

接者，我們終於可以來解迴圈了! 如果最優策略始於A且終於A，那我們的初始化條件是：rmax(1,1)=0 ,rmax(1,2)=-∞, rmax(1,3)=-∞, pres(T+1,s)=1。給定rmax(t-1,1), rmax(t-1,2), rmax(t-1,3)，就可以算出rmax(t,s)和相對應的pres(r,s)，也就是可以做出正確的選擇，根據時間t=T-1的決策s和pre(T-1,s)，我們可以得到t=T-2的決策，反覆逆推，可以得到t=1到T的所有決策，就可以得到始於A且終於A的策略，我們就可以依此得到始於{A,B,C}選任一，終於{A,B,C}選任一的最優策略，接者就可以算出在所有可能的初始條件下的最優解。因此，正向求解rmax(t,s)需要的計算次數是O(3T), 逆向找最佳解的過程計算次數維O(T)，如果資產選擇的數量是B，那麼我需要的計算次數為O(NT+T)，因為我可以先行儲存從任一時間點到下一時間點的最優解策略。同時，我也發現這方法的存儲空間需要量也是O(NT)，因此算是一種很節省空間和時間的策略。

三-二、求解(有交易次數限制)

我發現當題目條件設置嚴苛的情況下，我們確實可以很簡單的在線性時間內找到最佳策略，當我在推演的過程中，才發現如果每期個別資產的報酬率為已知的情況下，我們可以用相對簡單的動態規劃得到最佳解，因此我決定幫自己增加一些限制，來讓DP的運算過程受到阻礙，並嘗試找到相對應的最佳解。

因此，我決定將自己的交易次數增加限制，我只能夠轉換M次，M<T。我們用小m來代表目前的累計交易次數，m<=M。如果在t-1期投資者持有A，那t期累積的交易次數可能是m-1(繼續持有A)或者是m(改成持有B或C)，因此，到時間t為止投資者所獲得的總收益率是rmax(t-1,m,1)+ rA t，1是S (rmax(T,M,S))，如果原本是B轉變成A，則是rmax(t-1,m-1,2)+ rA t-α；如果原本是C轉變成A，則是rmax(t-1,m-1,3)+ rA t-α。很類似地，我們可以將rmax表示成這樣：

rmax(t,m,1) = max(rmax(t-1,m,1)+ rA t, rmax(t-1,m-1,2)+ rA t-α, rmax(t-1,m-1,3)+ rA t-α) (6)

接者，我們在可以來表示在t-1期時，如果在第T期選擇資產A的話，應該選擇持有的標的：

Pres(t,m,1) = {(m,1) if rmax(t,m,1) = rmax(t-1,m,1)+ rA t , (m-1, 2) if rmax(t,m,1) = rmax(t-1,m-1,2)+ rA t -α, (m-1, 3) if rmax(t,m,1) = rmax(t-1,m-1,3)+ rA t -α} (7)

這裡的變數比較多，我們分三個狀況來討論。如果在第T期選擇資產B的話，我們有：

rmax(t,m,2) = max(rmax(t-1,m-1,1)+ rB t -α, rmax(t-1,m-1,2)+ rB t, rmax(t-1,m-1,3)+ rB t-α) (8)

Pres(t,m,2) {(m-1,1) if rmax(t,m,2) = rmax(t-1,m-1,1)+ rB t -α , (m, 2) if rmax(t,m,2) = rmax(t-1,m,2)+ rB t, (m-1, 3) if rmax(t,m,2) = rmax(t-1,m-1,3)+ rB t -α} (9)

如果在第T期選擇資產C的話，我們有：

rmax(t,m,3) = max(rmax(t-1,m-1,1)+ rC t -α, rmax(t-1,m-1,2)+ rC t-α, rmax(t-1,m,3)+ rC t -α) (10)

Pres(t,m,3) {(m-1,1) if rmax(t,m,3) = rmax(t-1,m-1,1)+ rC t -α , (m-1, 2) if rmax(t,m,3) = rmax(t-1,m-1,2)+ rC t, (m, 3) if rmax(t,m,3) = rmax(t-1,m,3)+ rC t -α} (11)

假設最優策略開始於A，我們的初始條件擴展為：

rmax(1,0,1)=0, rmax(1,0,2)= -∞, rmax(1,0,3)= -∞, rmax(1,1,1)= -∞, rmax(1,1,2)= -∞, rmax(1,1,3)= -∞,

根據6到11所顯示的部分，對於t ∈[1,2,3…,T], s ∈{1,2,3}, m∈[0,1,2,…,M]，我們可以計算出所有的rmax(t,m,s)跟pre(t,m,s)，我們可以推算說我們的時間複雜度是原本狀況乘上各式M來當作探索不同交易次數限制的狀況。

當t=T時，如果最後的總交易次數等於最大允許的交易次數M，那麼當t=T時，m=M, s=1, pres(T,M,1) 給出了前一個時間點t=T-1時m跟s的取值。根據t=T-1時的m跟s的取值以及剛剛求得的pre(T-1,m,s)，我們可以得到t=T-2時s跟m的取值，依此類推，我們可以得到在各式情況下(m,s的組合)，於t ∈[1,2,3…,T]時的pres值。

根據剛剛的討論，如果可供選擇的資產數量為N，計算過程求解rmax(t,s)會花O(MNT)，逆向尋找最佳解的計算次數維O(MT)，總體計算次數維O(MNT+MT)，可以用O(MNT)表示。同理，我們也可以得到實際交易次數等於0,1,2…M-1時的局部最佳交易解。透過對比，我們可以得到所有策略的總收益率，接者就能夠獲得所有情況下可抵達的最佳解了。

四、心得：

在這次的研究中，我探討了一開始設定的問題：當報酬率已知時，是否能夠在足夠好的時間內，找到在不同時間內最適合的資產配置。除了總報酬外，大多數的資產配置績效評估也考慮到風險，例如夏普值。由於夏普值在時間上不具有可加性或可乘性，可能需要進一步討論或參考其他文獻，才能有更實際的應用。

雖然我認為這份報告還有很多可以改進的地方。例如，我的背景設定可能過於強調，在實際應用中可能不太適用。此外，如何選擇不同的資產配置組合，以及這些組合在不同時間點的預期績效，在本研究中並未探討（這可能更屬於傳統金融領域）。然而，我們成功地利用動態規劃策略找到了如何在不同的資產組合中進行資產轉移的方法。

我認為這份報告中最重要的發現之一是，資產組合的增加並不會增加其複雜性（因為組合數量是線性的）。因此，我們可以嘗試許多不同的資產配置組合，並在這些大量的組合中找到最合適的配置。這樣一來，我們就可以模擬真實情況，在機器人理財中找到在某些特定條件下，不同時間點應該選擇的資產組合。