Check the proof and assumptions for linear IRL

[JinraeKim]

Linear IRL [1, 2] 의 수렴성 및 그에 필요한 조건을 확인한다

• [x] 기법 특성 (e.g. online, model-free, linear, etc.)
• [x] 수렴 조건

Refs

[1] D. Vrabie, O. Pastravanu, M. Abu-Khalaf, and F. L. Lewis, “Adaptive optimal control for continuous-time linear systems based on policy iteration,” Automatica, vol. 45, no. 2, pp. 477–484, Feb. 2009, doi: 10.1016/j.automatica.2008.08.017. [2] “Reinforcement Learning and Feedback Control: Using Natural Decision Methods to Design Optimal Adaptive Controllers,” IEEE Control Syst., vol. 32, no. 6, pp. 76–105, Dec. 2012, doi: 10.1109/MCS.2012.2214134.

[JinraeKim]

[1] 논문의 내용상으로는, 제안된 policy iteration 기법은 Kleinman 알고리즘 (a.k.a. Newton method) 에 기반한 offline iteration-based algorithm 이다.

기법 특성

• Offline online 데이터 from a single trajectory 를 이용
• model-based partially model-free (x_dot = Ax + Bu 에서 B 만 필요)
• • Kleinman algorithm 기반 (Newton method 의 속도로 수렴; quadratic convergence)

한계점

• Initial stabilising gain K_i 필요
• Online 데이터를 이용하여 Kleinman 업데이트를 할 때, 전체적인 시간에 대한 게인 K := K_i for t \in [t_i, t_{i+1}) 의 안정성에 대한 분석은 결여된 것으로 보임
• Next critic parameter 를 구하기 위해 least-square 를 취할 때, 온라인 데이터가 충분히 full rank matrix 를 형성할 것인가?

[hnlee77]

기법 특성

• Offline
• [ ] (조금 헷갈리는데, 맞나요? @hnlee77) model-based

기법은 online이고, partially model-free가 맞을 것 같습니다.

[JinraeKim]

기법이 왜 online 이죠? Offline 기법을 안정성 분석 없이 online 으로 쓴 것으로 보이는데...

[hnlee77]

실시간으로 궤적추종을 하며 얻어지는 데이터를 이용하니까요?

[JinraeKim]

음... 그럼 online 에서의 안정성 분석이 결여되었지만 online 으로 썼으니까 online 기법이라고... 해야할까요 애매하네요 ㅠ

[JinraeKim]

실시간으로 궤적추종을 하며 얻어지는 데이터를 이용하니까요?

궤적 추종을 하나요?

[hnlee77]

기법이 왜 online 이죠? Offline 기법을 안정성 분석 없이 online 으로 쓴 것으로 보이는데...

offline기법을 안정성 분석 없이 online으로 썼다는 것은.. 잘 이해를 못했습니다. 제가 생각하기에는 데이터 관점에서 온라인으로 얻어지는 데이터를 사용하여 업데이트를 하면 online 기법으로 보는 게 맞을 것 같습니다.. 안정성 분석은 다른 얘기?

[hnlee77]

실시간으로 궤적추종을 하며 얻어지는 데이터를 이용하니까요?

궤적 추종을 하나요?

미안함다.. regulation 문제이지만 regulation 궤적을 따라간다는 의미로 사용했습니다.

[JinraeKim]

미안함다.. regulation 문제이지만 regulation 궤적을 따라간다는 의미로 사용했습니다.

아하 제가 논문을 읽어본지 얼마 안되서 잘 몰라서 물어봤습니다. 이해되었습니다. 감사합니다 ㅎ

offline기법을 안정성 분석 없이 online으로 썼다는 것은.. 잘 이해를 못했습니다. 제가 생각하기에는 데이터 관점에서 온라인으로 얻어지는 데이터를 사용하여 업데이트를 하면 online 기법으로 보는 게 맞을 것 같습니다..

그렇다면, online 에서의 안정성이 보장되지 않은 online 기법이라고 하면 될까요?

[JinraeKim]

기법은 online이고, partially model-free가 맞을 것 같습니다.

아, B matrix 만 필요하니 partially model-free 가 적절하겠네요!

[hnlee77]

그렇다면, online 에서의 안정성이 보장되지 않은 online 기법이라고 하면 될까요?

이렇게 하면 혼동이 덜 될 것 같습니다 ㅎㅎ

[JinraeKim]

• Online 데이터를 이용하여 Kleinman 업데이트를 할 때, 전체적인 시간에 대한 게인 K := K_i for t \in [t_i, t_{i+1}) 의 안정성에 대한 분석은 결여된 것으로 보임

@hnlee77 이렇게 밝히면 괜찮을까요?

[hnlee77]

좋습니다.

[JinraeKim]

Closed as it's completed

[JinraeKim]

@hnlee77 뭔가 이상한 부분을 찾았는데, 잘 이해가 안가서 질문을 남깁니다 (issue re-opened).

[1] 에서, 기법을 policy iteration (PI) 와 value iteration (VI) 로 나누고 있습니다:

PI, VI 분류

  

어떻게 위처럼 PI, VI 가 나눠지는 것이죠?

제가 이해하기로는 (강화학습 분야에서 공부했을 때는),

1. PI 는 "특정 iteration 에서의 policy 가 주어지면" 그에 대한 expected value 를 계산하고 (policy evaluation), 이에 대해 greedy 한 policy 로 업데이트하고 (policy improvement) 를 반복하는 것으로 알고 있습니다. 그런 맥락에서 식 (94), (96) 는 이해가 됩니다.
2. VI 는 "특정 policy 를 잡지 않고", "greedy"하게 value 를 업데이트하는 것으로 알고 있습니다. 식 (97), (96) 은 이미 그 "greedy" 하게 value 를 업데이트한다는 것이, (96) 처럼 mu_i 에 녹아있어서 VI 로 보는 것일까요?

왜 VI 는 initial stabilising gain 이 아니어도 된다고 써있을까요?

참고로 [1] 에는, [2] 에 policy iteration 의 수렴성이 증명되어있다고 언급합니다. (당연히) [2]는 Kleinman 알고리즘을 기반으로 하기에 initial stabilising gain 을 필요로 합니다. 근데 VI 는 아무 gain 을 잡아도 된다고 되어있고, 수렴성 증명에 대한 언급이 없습니다. 혹시 관련 논문을 아실까요? 참고로 코드상으로 구현된 것 (#18) 은 VI 식 with approximation & online implementation 을 이용하였습니다 (식 (99) 및 (96))

VI with approx. (online version)


EDIT: [2] 의 Lemma 3 을 어떻게 유도할 수 있나요? 잘 안 되서...

[2, Lemma 3]

 

Refs

[1] “Reinforcement Learning and Feedback Control: Using Natural Decision Methods to Design Optimal Adaptive Controllers,” IEEE Control Syst., vol. 32, no. 6, pp. 76–105, Dec. 2012, doi: 10.1109/MCS.2012.2214134. [2] D. Vrabie, O. Pastravanu, M. Abu-Khalaf, and F. L. Lewis, “Adaptive Optimal Control for Continuous-Time Linear Systems Based on Policy Iteration,” Automatica, vol. 45, no. 2, pp. 477–484, Feb. 2009, doi: 10.1016/j.automatica.2008.08.017.

[hnlee77]

@hnlee77 뭔가 이상한 부분을 찾았는데, 잘 이해가 안가서 질문을 남깁니다 (issue re-opened).

[1] 에서, 기법을 policy iteration (PI) 와 value iteration (VI) 로 나누고 있습니다:

어떻게 위처럼 PI, VI 가 나눠지는 것이죠?

제가 이해하기로는 (강화학습 분야에서 공부했을 때는),

1. PI 는 "특정 iteration 에서의 policy 가 주어지면" 그에 대한 expected value 를 계산하고 (policy evaluation), 이에 대해 greedy 한 policy 로 업데이트하고 (policy improvement) 를 반복하는 것으로 알고 있습니다. 그런 맥락에서 식 (94), (96) 는 이해가 됩니다.
2. VI 는 "특정 policy 를 잡지 않고", "greedy"하게 value 를 업데이트하는 것으로 알고 있습니다. 식 (97), (96) 은 이미 그 "greedy" 하게 value 를 업데이트한다는 것이, (96) 처럼 mu_i 에 녹아있어서 VI 로 보는 것일까요?

저도 이 논문에서 주장하는 VI의 알고리즘에 이런 의문을 갖고있었는데요. 말씀하신 내용대로 greedy한 업데이트를 한꺼번에 보는 것이겠다고 생각을 했습니다.

왜 VI 는 initial stabilising gain 이 아니어도 된다고 써있을까요?

참고로 [1] 에는, [2] 에 policy iteration 의 수렴성이 증명되어있다고 언급합니다. (당연히) [2]는 Kleinman 알고리즘을 기반으로 하기에 initial stabilising gain 을 필요로 합니다. 근데 VI 는 아무 gain 을 잡아도 된다고 되어있고, 수렴성 증명에 대한 언급이 없습니다. 혹시 관련 논문을 아실까요? 참고로 코드상으로 구현된 것 (#18) 은 VI 식 with approximation & online implementation 을 이용하였습니다 (식 (99) 및 (96))

이에 대한 자세한 증명을 본 논문은 없습니다. 이와 관련해서 VI 알고리즘의 수렴성과 같은 내용을 더 알아보고자 Tao Bian의 논문 등을 찾게 된 것이었고(이후에 같이 리뷰함), 이 외에는 보지 못했습니다.

EDIT: [2] 의 Lemma 3 을 어떻게 유도할 수 있나요? 잘 안 되서...

저는 이 논문 자체를 깊게 읽어보지 않아서 증명을 모두 따라가보지 않았는데 먼저 살펴본 후에 얘기해볼게요.

[seong-hun]

2. VI 는 "특정 policy 를 잡지 않고", "greedy"하게 value 를 업데이트하는 것으로 알고 있습니다. 식 (97), (96) 은 이미 그 "greedy" 하게 value 를 업데이트한다는 것이, (96) 처럼 mu_i 에 녹아있어서 VI 로 보는 것일까요?

저는 VI는 특정 policy를 잡지 않는 기법이라기 보다는 특정 policy에 대한 value를 구하지는 않는다라고 이해하고 있습니다 (Sutton and Barto, 2018). 만약에 (97)에서 V_j 대신 V_{j+1} 이 들어간다면 V_{j+1}는 policy \mu_j에 대한 value function이 될 겁니다. 하지만 (97)의 V_{j+1}은 이런 exact value function이 아니라 그냥 어떤 function입니다. Policy evaluation 단계에서는 이 어떤 function V_{j+1}에 대해서 (96)을 써서 \mu_{j+1}을 구합니다.

정리하자면, PI 기법은 어떤 policy에 대한 exact value function을 매번 구해나가면 결국 policy와 value function들이 최적값으로 수렴하기를 원하는 기법이고, VI 기법은 그냥 어떤 function V_j들을 구해나갔더니, V_j와 (96)으로 구한 policy가 각각 optimal value function과 최적제어입력으로 수렴하기를 원하는 기법이라고 생각됩니다.

사실 이로부터 다음 질문에 대한 대답도 바로 가능합니다.

왜 VI 는 initial stabilising gain 이 아니어도 된다고 써있을까요?

왜냐하면 이 논문에서 정의하는 value function은 admissible policy일 때에만 잘 정의되기 때문입니다. 따라서 PI는 value function을 매번 구해야 하기 때문에 admissible policy가 필요하고, VI는 value function이 아닌 어떤 function V_j를 구하기 때문에 이런 제약에서 자유로운 것 같습니다.

[JinraeKim]

설명이 깔끔해서 이해가 잘 되었습니다.

그럼 Tao Bian 의 CT VI ADP (#20)는, 처음 제안된 VI 가 아니라 새로 제안된 VI 인 것이군요. 물론 선형 비선형 차이가 있겠지만...

혹시 linear IRL 의 VI 버전의 수렴성에 대한 논문이나, 증명 같은 것은 보거나 유도해본 적이 있을까요?

[seong-hun]

그럼 Tao Bian 의 CT VI ADP (#20)는, 처음 제안된 VI 가 아니라 새로 제안된 VI 인 것이군요. 물론 선형 비선형 차이가 있겠지만...

그렇습니다. 처음 제안된 것은 (아마도) [1]인 것 같고, [2]에서 조금 더 확장합니다 (둘 다 선형).

[1] D. Vrabie and F. L. Lewis, “Generalized Policy Iteration for continuous-time systems,” in 2009 International Joint Conference on Neural Networks, Atlanta, Ga, USA, Jun. 2009, pp. 3224–3231. doi: 10.1109/IJCNN.2009.5178964.

[2] J. Y. Lee, J. B. Park, and Y. H. Choi, “On integral generalized policy iteration for continuous-time linear quadratic regulations,” Automatica, vol. 50, no. 2, pp. 475–489, Feb. 2014, doi: 10.1016/j.automatica.2013.12.009.

[JinraeKim]

시간날 때 슬쩍 봐야겠군요~

[JinraeKim]

[1] D. Vrabie and F. L. Lewis, “Generalized Policy Iteration for continuous-time systems,” in 2009 International Joint Conference on Neural Networks, Atlanta, Ga, USA, Jun. 2009, pp. 3224–3231. doi: 10.1109/IJCNN.2009.5178964.

이건 좀 읽어보니, VI variant 라고 나온 기법도 initial stabilising gain 이 필요하네요. 참고로 해당 논문에서는 Generalised PI, GPI 에 k=1 을 대입한 것을 VI variant 로 표현하고 있습니다. 그래서 VI 와 VI variant 의 차이로, VI 는 initial stabilising gain 이 필요없고, VI variant 는 필요하다는 것을 언급하네요:

일단 initial stabilising gain 가정은 이 VI (variant) 에서도 필요해보이네요.

혹시 잘못 이해한 부분이 있으면 지적 부탁드립니다~

[seong-hun]

넵 맞습니다. 다음 논문에서 이것을 단점으로 지적하며 GPI에 대해서 initial admissible policy가 필요없도록 확장합니다.

[2] J. Y. Lee, J. B. Park, and Y. H. Choi, “On integral generalized policy iteration for continuous-time linear quadratic regulations,” Automatica, vol. 50, no. 2, pp. 475–489, Feb. 2014, doi: 10.1016/j.automatica.2013.12.009.

[JinraeKim]

그게 바로 다음 논문이었구만~