2025-11-10T02:30:58.102691

Finite-time Convergence Analysis of Actor-Critic with Evolving Reward

Hu, Chen, Huang

Many popular practical reinforcement learning (RL) algorithms employ evolving reward functions-through techniques such as reward shaping, entropy regularization, or curriculum learning-yet their theoretical foundations remain underdeveloped. This paper provides the first finite-time convergence analysis of a single-timescale actor-critic algorithm in the presence of an evolving reward function under Markovian sampling. We consider a setting where the reward parameters may change at each time step, affecting both policy optimization and value estimation. Under standard assumptions, we derive non-asymptotic bounds for both actor and critic errors. Our result shows that an $O(1/\sqrt{T})$ convergence rate is achievable, matching the best-known rate for static rewards, provided the reward parameters evolve slowly enough. This rate is preserved when the reward is updated via a gradient-based rule with bounded gradient and on the same timescale as the actor and critic, offering a theoretical foundation for many popular RL techniques. As a secondary contribution, we introduce a novel analysis of distribution mismatch under Markovian sampling, improving the best-known rate by a factor of $\log^2T$ in the static-reward case.

academic

진화하는 보상을 갖는 Actor-Critic의 유한시간 수렴 분석

기본 정보

논문 ID: 2510.12334
제목: Finite-time Convergence Analysis of Actor-Critic with Evolving Reward
저자: Rui Hu, Yu Chen, Longbo Huang (청화대학교 IIIS)
분류: cs.LG (기계학습), cs.AI (인공지능)
발표 시간: 2025년 10월 14일 (arXiv 사전인쇄본)
논문 링크: https://arxiv.org/abs/2510.12334v1

초록

많은 인기 있는 강화학습 알고리즘은 보상 형성, 엔트로피 정규화 또는 커리큘럼 학습 등의 기법을 통해 진화하는 보상 함수를 채택하지만, 그 이론적 기초는 여전히 불완전하다. 본 논문은 마르코프 샘플링 하에서 진화하는 보상 함수가 존재할 때 단일 시간 척도 Actor-Critic 알고리즘의 유한시간 수렴 분석을 처음으로 제공한다. 본 연구는 보상 매개변수가 매 시간 단계마다 변할 수 있는 설정을 고려하며, 이는 정책 최적화와 가치 추정에 모두 영향을 미친다. 표준 가정 하에서 Actor와 Critic 오차의 비점근적 경계를 도출한다. 결과는 보상 매개변수 진화가 충분히 느린 조건 하에서 $O(1/\sqrt{T})$ 의 수렴률을 달성할 수 있음을 보여주며, 이는 정적 보상의 최적 알려진 률과 일치한다. 보상이 Actor 및 Critic과 동일한 시간 척도에서 유계 기울기를 갖는 기울기 기반 규칙을 통해 업데이트될 때, 이 수렴률이 유지되어 많은 인기 있는 강화학습 기법에 대한 이론적 기초를 제공한다.

연구 배경 및 동기

문제 배경

이론과 실제의 격차: 강화학습 이론은 일반적으로 정적 보상 함수의 마르코프 결정 과정(MDP)을 기반으로 하지만, 실제 응용에서는 진화하는 보상 기법이 광범위하게 사용된다
진화하는 보상의 보편성: 실제 RL 알고리즘에서 보상 형성, 엔트로피 정규화, 커리큘럼 학습 등의 기법이 학습 효과를 개선하기 위해 널리 채택된다
설계 과제: 실제 시나리오에서 학습 가능하면서도 원하는 작업과 일치하는 보상 함수를 설계하는 것은 상당한 어려움이 있다

핵심 문제

RL 알고리즘의 수렴성을 보장하면서 보상 함수가 얼마나 빠르게 변할 수 있는가?

기존 방법의 한계

기존 이론 분석은 주로 정적 보상 설정에 집중되어 있다
진화하는 보상 하에서 Actor-Critic 알고리즘의 수렴성에 대한 이론적 보장이 부족하다
마르코프 샘플링 하에서의 분포 불일치 분석이 개선될 여지가 있다

핵심 기여

획기적 이론 분석: 진화하는 보상 하에서 단일 시간 척도 Actor-Critic 알고리즘의 첫 번째 유한시간 수렴 분석을 제공한다
수렴률 보장: 보상 매개변수 진화가 충분히 느린 조건 하에서 $O(1/\sqrt{T})$ 수렴률을 달성할 수 있음을 증명하며, 이는 정적 보상의 경우와 일치한다
실용성 검증: 기울기 기반 보상 업데이트 규칙이 수렴 조건을 만족함을 증명하여 실제 RL 기법에 이론적 지원을 제공한다
기술 개선: 마르코프 샘플링 하에서 새로운 분포 불일치 분석을 도입하여 정적 보상의 경우 수렴률을 $\log^2 T$ 인수만큼 개선한다

방법 상세 설명

작업 정의

무한 지평선 할인 마르코프 결정 과정 $M = (S,A,P,r,\gamma)$ 를 연구하며, 여기서 보상 함수 $r$ 은 시간에 따라 진화할 수 있다. 목표는 진화하는 보상 설정 하에서 Actor-Critic 알고리즘의 수렴성을 분석하는 것이다.

모델 아키텍처

1. 진화하는 보상 프레임워크

정규화된 보상 $\tilde{r}_{\phi,\theta}(s,a)$ 를 결정하는 모든 요소를 포함하는 일반 보상 매개변수 $\phi$ 를 도입한다: $\tilde{r}_{\phi,\theta}(s,a) = r(s,a) - \alpha \log \pi_\theta(a|s)$

여기서 $\alpha \geq 0$ 은 엔트로피 정규화 매개변수이다.

2. Actor-Critic 업데이트 규칙

Actor 업데이트: $\theta_{t+1} \leftarrow \theta_t + \eta_t^\theta \hat{\delta}_t \nabla_\theta \log \pi_\theta(a_t|s_t)$

Critic 업데이트: $\omega_{t+1} \leftarrow \text{Proj}_{C_\omega}(\omega_t + \eta_t^\omega \hat{\delta}_t \phi(s_t))$

여기서 시간차 오차는 다음과 같다: $\hat{\delta}_t = \tilde{r}_{\phi_t,\theta_t}(s_t,a_t) + (\gamma\phi(s'_t) - \phi(s_t))^\top \omega_t$

3. 마르코프 샘플링 정책

샘플링 커널 $\hat{P}(\cdot|s,a) = \gamma P(\cdot|s,a) + (1-\gamma)\rho(\cdot)$ 를 채택하여 에르고딕성을 보장한다.

기술 혁신 포인트

1. 진화하는 보상의 립시츠 연속성 분석

정책 목표 $J_\phi(\theta)$ 와 최적 Critic 매개변수 $\omega^*(\phi,\theta)$ 의 보상 매개변수 $\phi$ 에 대한 립시츠 연속성을 확립한다:

$J_\phi(\theta)$ 는 $\phi$ 에 대해 $D_J$ -립시츠이다
$\omega^*(\phi,\theta)$ 는 $\phi$ 에 대해 $D_\omega$ -립시츠이다

2. 새로운 분포 불일치 분석

유도된 연산자의 상태 분포에 대한 축약 성질을 직접 활용하는 핵심 명제 4.8을 제시한다: $E\|\hat{\nu}_t - \nu_\rho^{\pi_{\theta_t}}\|_1 \leq LC_\delta L_\nu \sum_{k=0}^{t-1} \gamma^{t-1-k}\eta_k^\theta + \gamma^t\|\rho - \nu_\rho^{\pi_{\theta_0}}\|_1$

3. 체계적 부등식 해결

대수 부등식 $2\sqrt{G_T W_T} \leq \frac{1-\gamma}{2L}G_T + \frac{2L}{1-\gamma}W_T$ 를 통해 Actor와 Critic 오차를 분리한다.

실험 설정

이론 분석 프레임워크

본 논문은 주로 이론 분석을 수행하며 다음 설정을 채택한다:

평가 지표

Actor 오차: $G_T = \frac{1}{T/2}\sum_{t=T/2}^{T-1} E\|\nabla_\theta J_{\phi_t}(\theta_t)\|_2^2$
Critic 오차: $W_T = \frac{1}{T/2}\sum_{t=T/2}^{T-1} E\|\omega_t - \omega_t^*\|_2^2$
보상 변화: $F_T = \frac{1}{T/2}\sum_{t=T/2}^{T-1} E\|\phi_{t+1} - \phi_t\|_2^2$

핵심 가정

충분한 탐색 (가정 4.1): 모든 $\theta \in \Omega(\theta)$ 에 대해 $A_\theta$ 는 음정치이고 특이값 상한은 $-\lambda$ 이다
정책 립시츠 연속성 (가정 4.3): $\|\nabla_\theta \log \pi_\theta(a|s)\|_2 \leq L$
정규화 보상 립시츠 연속성 (가정 4.5): $\phi$ 에 대한 립시츠 상수는 $D$ 이다

실험 결과

주요 이론 결과

정리 4.6 (주요 수렴 정리)

단계 크기 $\eta_t^\theta = \frac{c_\theta}{\sqrt{t}}$ 와 $\eta_t^\omega = \frac{c_\omega}{\sqrt{t}}$ 이고 $\frac{c_\theta}{c_\omega} \leq \frac{\lambda}{LS_\omega} \wedge \frac{1}{16LL_\omega}$ 인 조건 하에서:

$G_T = O\left(\frac{1}{\sqrt{T}}\right) + O\left(F_T\sqrt{T}\right) + O\left(\sqrt{\frac{F_T}{T}}\right) + O(\epsilon)$

$W_T = O\left(\frac{1}{\sqrt{T}}\right) + O\left(F_T\sqrt{T}\right) + O\left(\sqrt{\frac{F_T}{T}}\right) + O(\epsilon)$

추론 4.7 (기울기 업데이트 규칙)

보상 매개변수가 기울기 업데이트 규칙 $\phi_{t+1} \leftarrow \phi_t + \eta_t^\phi h_\phi(t)$ 를 채택하고, $E\|h_\phi(t)\|_2^2 \leq C_\phi^2$ , $\eta_t^\phi = \frac{c_\phi}{t}$ 일 때:

$F_T = O\left(\frac{1}{T}\right) \Rightarrow G_T = O\left(\frac{1}{\sqrt{T}}\right) + O(\epsilon), \quad W_T = O\left(\frac{1}{\sqrt{T}}\right) + O(\epsilon)$

핵심 발견

1. 수렴 조건

점근 수렴: $F_T = o(1/\sqrt{T})$ 이 필요하다
$O(1/\sqrt{T})$ 수렴률 유지: $F_T = O(1/T)$ 이 필요하다

2. 정적 보상의 경우 개선

$F_T \equiv 0$ 일 때, 알고리즘은 표준 $O(1/\sqrt{T})$ 수렴률을 달성하며, 이전 연구에 비해 $\log^2 T$ 인수를 제거한다.

3. 실용성 검증

호기심 기반 보상 형성, 무작위 네트워크 증류, 소프트 Actor-Critic 자동 엔트로피 조정을 포함한 광범위한 실제 기법이 이론적 보장 조건을 만족함을 증명한다.

결론 및 논의

주요 결론

단일 시간 척도 Actor-Critic 알고리즘은 보상 비정상성에 대해 상당한 견고성을 보인다
보상 매개변수 진화 속도를 제어하는 조건 하에서 표준 $O(1/\sqrt{T})$ 수렴률을 유지할 수 있다
기울기 기반 보상 업데이트는 이론적 보장 조건을 만족하여 실제 성공에 대한 이론적 기초를 제공한다

한계

분석은 선형 함수 근사의 Critic으로 제한된다
립시츠 연속성 등의 표준 가정을 만족해야 한다
보상 변화 속도가 엄격하게 제어되어야 한다

향후 방향

비선형 함수 근사, 특히 신경망으로 확장
이론적 발견이 더 효과적이고 증명 가능하게 안정적인 보상 형성 알고리즘 설계에 미치는 영향 탐색
동적 목표 하에서의 강화학습 분석 (진화하는 보상, 변화하는 초기 분포 또는 전이 확률)

심층 평가

장점

획기적 기여: 진화하는 보상 하에서 Actor-Critic 알고리즘에 대한 이론 분석을 처음으로 제공한다
기술적 엄밀성: 증명 과정이 완전하고 가정이 합리적이며 분석이 깊이 있다
실용적 가치: 광범위하게 사용되는 RL 기법에 이론적 지원을 제공한다
방법 혁신: 분포 불일치 분석의 개선는 독립적인 가치를 갖는다

부족한 점

적용 범위: 선형 함수 근사로만 제한되며, 실제 응용은 대부분 심층 신경망을 사용한다
가정 제한: 립시츠 연속성 등의 가정이 실제로 검증하기 어려울 수 있다
실험 검증: 이론 결과를 검증하는 수치 실험이 부족하다

영향력

이론적 기여: 진화하는 보상 RL 이론 분석의 공백을 채운다
실제 지침: 알고리즘 설계에 이론적 지침 원칙을 제공한다
후속 연구: 더 복잡한 설정으로의 확장을 위한 기초를 마련한다

적용 시나리오

이론적 보장이 필요한 RL 알고리즘 설계
보상 형성 및 커리큘럼 학습의 이론 분석
자적응 엔트로피 정규화 알고리즘의 수렴성 연구

참고문헌

논문은 강화학습 이론 분석 분야의 중요한 연구를 인용하고 있으며, 다음을 포함한다:

Sutton & Barto (1998): 강화학습 기초 이론
Chen et al. (2021), Olshevsky & Gharesifard (2023): 단일 시간 척도 Actor-Critic 분석
Haarnoja et al. (2018): 소프트 Actor-Critic 알고리즘
Pathak et al. (2017): 호기심 기반 탐색

전체 평가: 이것은 고품질의 이론 논문으로, 진화하는 보상 하에서 Actor-Critic 알고리즘에 대한 엄격한 수렴성 분석을 처음으로 제공한다. 적용 범위에서 일정한 한계가 있지만, 이론적 기여는 상당하며 실제 RL 알고리즘의 이해와 설계를 위한 중요한 이론적 기초를 제공한다.