arXiv:2610.02520v1 cs.LG

단계별 제약 조건이 있는 CMDP를 위한 인스턴스 의존적 후회도

Instance-Dependent Regret for CMDPs with Step-Wise Constraints

Qian Zuo, Francesco Emanuele Stradi, Leyang Xue, Sattar Vakili

제출 2026-10-01

한국어 초록

본 논문에서는 단계별 안전 제약 조건(step-wise safety constraints)을 갖는 에피소드형 테이블 형식의 제약 마르코프 결정 과정(CMDP)에서의 온라인 학습을 연구합니다. 이러한 환경에서 제약 조건은 실행 가능한 정책 하에서 누적 보상의 분산을 결정하고, 결과적으로 학습 난이도를 형성하는 안전한 부분 그래프(safe subgraph)를 유도합니다. 그러나 이러한 구조를 활용하려면 제약 위반을 제어하면서 어떤 행동이 안전한지 학습해야 합니다. 우리는 후보 안전 부분 그래프를 학습하고 그 안에서 분산 적응형 낙관적 계획을 수행하는 효율적인 알고리즘인 SVAE(Safe Variance-Adaptive Exploration)를 제안합니다. SVAE는 높은 확률로 $K$개의 에피소드에 대해 $\widetilde{\mathcal{O}}(\sqrt{SAH\min\{\mathbb{V}_Σ,K\mathrm{Var}^{\star}\}}+S\sqrt{AH^3\min\{K,\mathcal{C}\}}+S^2AH^2)$ 차수의 누적 후회도(cumulative regret)를 달성하며, 여기서 $H$는 단일 에피소드의 기간(horizon), $S$와 $A$는 각각 상태 및 행동의 수입니다. 여기서 $\mathrm{Var}^{\star}$는 안전한 정책들 중 최대 수익 분산이고, $\mathbb{V}_Σ$는 첫 번째 불안전한 행동을 마주하기 전까지 누적된 분산이며, $\mathcal{C}$는 잠재적으로 안전하다고 잘못 간주된 행동을 제거하는 데 따르는 통계적 복잡도를 나타냅니다. 추가적으로 SVAE는 $\widetilde{\mathcal{O}}(H\sqrt{SAK}+S^2AH^2)$의 단계별 제약 위반과 $K$에 대해 다항 로그(polylogarithmic) 비례하는 갭 의존적(gap-dependent) 위반 상한을 달성합니다. 마지막으로, 이러한 인스턴스 특정 수치들에 대한 의존성이 불가피함을 보여주는 하한(lower bound)을 확립합니다.

원문 초록

We study online learning in episodic tabular constrained Markov decision processes with step-wise safety constraints. In such a setting, the constraints induce a safe subgraph that shapes the variance of cumulative rewards under feasible policies and, consequently, the difficulty of learning. Exploiting this structure, however, requires learning which actions are safe while controlling constraint violations. We propose Safe Variance-Adaptive Exploration (SVAE), an efficient algorithm that learns candidate safe subgraphs and performs variance-adaptive optimistic planning within them. With high probability, SVAE achieves cumulative regret of order $\widetilde{\mathcal{O}}(\sqrt{SAH\min\{\mathbb{V}_Σ,K\mathrm{Var}^{\star}\}}+S\sqrt{AH^3\min\{K,\mathcal{C}\}}+S^2AH^2)$ over $K$ episodes, where $H$ is the horizon of a single episode, while $S$ and $A$ are the numbers of states and actions, respectively. Here, $\mathrm{Var}^{\star}$ is the maximum return variance among safe policies, $\mathbb{V}_Σ$ is the variance accumulated before the first unsafe action is encountered, and $\mathcal{C}$ captures the statistical complexity of eliminating actions incorrectly considered potentially safe. SVAE additionally attains $\widetilde{\mathcal{O}}(H\sqrt{SAK}+S^2AH^2)$ step-wise constraint violation and a gap-dependent violation bound that is polylogarithmic in $K$. Finally, we establish a lower bound showing that dependence on these instance-specific quantities is unavoidable.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2610.02520v1

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2608.19779v2quant-ph공통 태그 Sequential Decision Making, reinforcement learning rl

월드 모델과 현실의 정렬에서 나타나는 기약 양자 이점

An Irreducible Quantum Advantage in Aligning World Models with Reality

월드 모델(world model)은 실제 세계의 디지털 시뮬라크르를 제공하여, 비용이 많이 드는 실제 환경 배치 이전에 에이전트(agent)를 학습하고 테스트할 수 있도록 돕는다. 각 타임스텝마다 월드 모델은 행동을 입력받아 실제 세계의 통계와 일치하는 관측값 및 보상(reward)을 생성한다. 현재의 결과가 먼 과거의 사건에 의존하는 복잡한 환경에서는 메모리가 필요하다. 흔히 메모리를 늘림으로써 실제 세계와 가상 세계의 최적 에이전트 정책을 정렬(alignment)할 수 있을 만큼 항상 충분히 정확한 모델을 구축할 수 있을 것이라 기대할 수 있다. 본 논문에서는 실제 세계 자체가 고전적(classical)일 때조차도 고전적 월드 모델에 대해서는 이러한 가정이 거짓임을 보인다. 연구진은 모든 유한 고전 모델이 동일한 가능한 궤적 상에서 실패하는 실제 세계들을 구성한다. 즉, 실제 세계가 특정 행동을 명확히 선호할 때 행동을 구분하는 능력을 상실하거나, 차선의 행동에 가장 높은 기대 보상을 반복적으로 부여한다. 또한 기대 보상 추정치에는 사라지지 않는 평균 오차가 지속적으로 남는다. 반면, 이러한 각각의 실제 세계는 단일 큐트리트(qutrit)를 사용하여 해당 환경을 정확히 재현하는 양자 월드 모델을 허용한다. 이 양자 모델의 보상 추정치와 선호 행동은 항상 실제 세계의 것과 일치하여, 실제 세계와 가상 세계의 최적 정책이 완벽하게 정렬되도록 보장한다.

arXiv:2610.02828v1cs.AI공통 태그 Sequential Decision Making, reinforcement learning rl

FSPO: 예산 제약 기반 LLM 강화학습 사후 학습을 위한 정책 일관적 위험 및 파레토 실행 가능 제어

FSPO: Policy-Consistent Risk and Pareto-Feasible Control for Budgeted LLM RL Post-Training

적응형 대규모 언어 모델(LLM) 강화학습(RL) 사후 학습은 롤아웃(rollout) 온도, 그룹 크기, 클리핑, KL 정규화(regularization), 검증기(verifier) 할당, 업데이트 예산 등 여러 학습 제어 요소를 온라인으로 변경합니다. 그러나 세 가지 결합된 문제가 여전히 해결되지 않은 상태로 남아 있습니다. 행동 궤적(behavior trajectories)으로 학습된 미래 위험 모델은 실제로 배포될 제어기(controller)가 유발하는 위험을 정확히 추정하지 못할 수 있고, 기록된 상태-행동 쌍에서 보정(calibrated)된 점수는 선택적 행동 결정 후 보정 오차가 발생할 수 있으며, 자원별 독립적인 최소 비용만으로는 일반적으로 다중 자원에 걸친 실행 가능한 지속 경로를 보장하지 못합니다. 본 논문에서는 이러한 문제들을 종합적으로 해결하는 예산 제약 기반 LLM RL 사후 학습용 피드백 상태 제어기인 FSPO를 제안합니다. FSPO는 향후 결정에 사용되는 동일한 동결 제어기를 벨만 타깃(Bellman target)으로 따르는 정책 일관적(policy-consistent) 잔여 위험(risk-to-go) 모델을 장기 효용 모델과 함께 학습합니다. 또한 결정 조건부 궤적 보정(DCTC)은 임시 제어기가 선택한 행동으로 생성된 교차 적합(cross-fitted) 궤적에서 위험을 보정합니다. 파레토 자원 지속 보증(PRCC)은 잔여 구간(horizon) 동안 비지배(non-dominated) 누적 예약이 실행 가능할 때만 행동을 허용합니다. 동일한 GRPO 자원 범위 조건에서 FSPO는 66.11%의 홀드아웃(held-out) 정확도와 59.43%의 OOD(분포 외) 정확도를 달성하여, 평가된 가장 강력한 적응형 기준선(baseline)인 PB2의 64.47% 및 57.03%를 능가했습니다. 3개의 쌍체 학습 시드(paired training seeds) 기준 홀드아웃 및 OOD 평가에서 문맥 밴딧(contextual bandit) 대비 각각 +2.42 및 +3.19%p 향상되었습니다. 행동-배포 간 불일치가 큰 조건에서 정책 일관적 위험은 선택 결정 ECE를 0.108에서 0.053으로 낮췄고, DCTC는 동일 수락률 조건에서 이를 0.039에서 0.022로 낮췄으며, PRCC는 18개 행동 카탈로그에서 거짓 실행 가능 허용을 완전히 제거했습니다($0.197\rightarrow0.000$). 요인 제거 분석(factorial ablation)에서 세 요소를 모두 활성화했을 때 궤적 실패율은 0.181에서 0.083으로 감소했습니다.

arXiv:2610.03634v1cs.AI공통 태그 Sequential Decision Making, reinforcement learning rl

핵심에 대한 보상: 터미널 에이전트를 위한 의존성 인식 정책 최적화

Credit Where It Matters: Dependency-Aware Policy Optimization for Terminal Agents

터미널을 사용하는 에이전트(agent)는 코딩, 디버깅 및 기타 다단계 터미널 작업에서 강화학습(RL)의 이점을 얻습니다. 이러한 작업에서는 후속 명령어가 이전 명령어에 의해 생성된 정보나 중간 결과에 의존하는 경우가 많습니다. 그러나 기존의 궤적 수준(trajectory-level) 및 단계 수준(step-level) 신용 할당(credit assignment) 방법은 명령어가 최종 결과에 영향을 미치는 읽기-쓰기 의존성을 명시적으로 추적하지 않습니다. 결과적으로 무관한 연산에도 학습(training) 신호가 할당되어 유의미한 단계로부터의 학습을 약화시킬 수 있습니다. 본 논문에서는 명령어 간의 실행 의존성을 활용하여 터미널 에이전트의 신용 할당을 안내하는 의존성 인식 그룹 정책 최적화(Dependency-Aware Group Policy Optimization, DepGPO)를 제안합니다. 구체적으로, 실행 추적(execution trace)으로부터 명령어 의존성 그래프를 구축하고 작업 검증기(task verifier)가 검사한 리소스에서부터 역방향으로 추적합니다. 그런 다음 이러한 경로를 따라 관련 쓰기 작업 및 이를 뒷받침하는 읽기 작업에 신용을 할당하고, 이를 활용해 단계별로 궤적 이점(trajectory advantage)을 재분배합니다. 광범위한 비교 실험과 절제 연구(ablation study)를 통해 DepGPO가 복잡한 터미널 작업에서 작업 성능과 학습 안정성을 향상시킴을 입증합니다.

arXiv:2610.00328v1cs.AI공통 태그 Sequential Decision Making, reinforcement learning rl

ContractRL: 감사 가능한 도구 호출 수정을 위한 보호된 그룹 상대적 정책 최적화

ContractRL: Shielded Group-Relative Policy Optimization for Auditable Tool-Call Repair

구조화된 도구 호출(tool call)은 종종 소수의 필드만이 스키마나 실행 계약(execution contract)을 위반하여 실패합니다. 객체 전체를 다시 생성하는 것은 행동 공간(action surface)을 확장시키고 반복적인 수정에 대한 감사를 어렵게 만듭니다. 본 논문에서는 검증기(verifier) 유도 JSON 수정을 유계 결정 과정(bounded decision process)으로 모델링하는 계약 제약 순차 수정 프로토콜인 ContractRL을 제안합니다. 각 단계에서 정책(policy)은 후보 객체, 타입이 지정된 검증기 피드백, JSON Pointer, 불변의 수정 이력, 남은 예산을 관찰하며, 결정론적 유효성 검사기가 상태 전이를 수행하기 전에 계약 기반 행동 마스크가 잘못되었거나 금지된 RFC-6902 연산을 필터링합니다. 또한 추적(trace)이 고정될 때까지 표준 타깃(canonical targets)과 시맨틱 라벨을 온라인 상태 외부에 유지하면서 패치, 재시도, 기권 결정을 위한 계약 제약 그룹 상대적 목적함수를 정의합니다. 동일한 검증기 정보 환경에서 시드당 192개 케이스와 5개의 시드에 걸쳐 평가한 결과, ContractRL은 34.4개의 생성 토큰으로 0.9362의 시맨틱 성공률을 달성하여, Patch-SFT의 0.9076 및 44.9개 토큰, 전체 재생성의 0.9148 및 137.2개 토큰과 대조적인 성과를 보였습니다. 정책 최적화(policy optimization)는 지도학습 기반 ContractRL의 시맨틱 성공률을 0.9186에서 0.9375로 향상시켰습니다. Patch-SFT와의 별도 3개 시드 대응 평가에서는 +0.0396의 시맨틱 차이(95% CI $[+0.0137,+0.0662], p=0.0039$)를 나타냈습니다. 피드백, 행동 마스크, 예산 및 스키마 변화(schema-shift) 분석은 이러한 성능 향상이 국소화된 교정(localized correction)과 연관되어 있음을 보여주며, 적대적 평가 및 다중 턴 평가는 남아 있는 실패 모드의 특성을 규명합니다.

arXiv:2610.00590v1cs.CR공통 태그 Sequential Decision Making, reinforcement learning rl

대규모 언어 모델을 활용한 계층적 사이버 방어를 향하여: 계획부터 실행까지

Towards Hierarchical Cyber Defense with Large Language Models: From Planning to Execution

강화학습(RL)으로 학습된 자율 사이버 방어 에이전트는 일반적으로 학습된 특정 네트워크에 종속되어 네트워크 규모가 변할 때 일반화 능력이 제한됩니다. 계층적 강화학습은 전략적 목표 설정과 전술적 실행을 분리하여 의사결정 복잡도를 줄이지만, 이러한 재학습 의존성을 완전히 제거하지는 못합니다. 본 연구에서는 파라미터가 고정된(frozen) 제로샷 대규모 언어 모델(LLM)이 계층적 사이버 방어에서 재학습이 필요 없는 제어를 제공할 수 있는지, 그리고 LLM 제어가 계획에서 실행으로 확장됨에 따라 성능이 어떻게 변화하는지 조사합니다. 우리는 계획자가 고정된 기간 동안 방어할 서브넷을 선택하고 실행자가 해당 서브넷 내에서 방어 행동을 선택하는 제어기 독립적(controller-agnostic) 계획자-실행자 계층 구조를 정식화합니다. MITRE ATT&CK 프레임워크와 매핑된 자동화된 레드팀 에이전트가 내장된 고충실도 Cyberwheel 환경을 활용하여, 소형, 중형, 대형 네트워크 전반에서 사이버 보안 특화 모델 2종을 포함한 3B~70B 파라미터 규모의 6개 모델을 바탕으로 RL+RL, LLM+RL, LLM+LLM 구성을 비교합니다. 계획자만 LLM으로 교체하는 것은 네트워크 크기가 커짐에 따라 제한적인 성능 향상만을 보였습니다. 반면, 실행 단계까지 LLM 제어를 확장하면 충분한 역량을 갖춘 모델에서 주목할 만한 성능 개선이 나타났습니다. 예를 들어, 고정된 범용 70B 모델은 RL 기준선이 각 규모마다 재학습되는 동안 동일한 모델 가중치를 사용하여 세 가지 네트워크 규모 모두에서 성공적인 횡적 이동(lateral movement) 비율을 약 1% 수준으로 억제하고 공격자 영향을 거의 0에 가깝게 유지했습니다. 본 연구 결과는 충분한 역량을 갖춘 고정된 LLM이 과제 특화 재학습 없이도 평가된 네트워크 규모 전반에 걸쳐 강력한 방어 성능을 유지할 수 있음을 보여주는 동시에, LLM 기반 제어의 이점을 실현하는 데 강력한 전술적 실행이 중요하다는 점을 시사합니다.

arXiv:2610.00979v1cs.AI공통 태그 Sequential Decision Making, reinforcement learning rl

RISED: 에이전트 다중 환경 선택 및 자기 증류를 위한 루브릭

RISED: RubrIcs for agentic multi-environment Selection and sElf-Distillation

다양한 상호작용 환경에서 단일 대규모 언어 모델(LLM) 에이전트를 공동으로 학습(training)시키는 것은 제너럴리스트 에이전트로 나아가는 경로로서 점점 더 많은 주목을 받고 있습니다. 기존의 커리큘럼 및 데이터 선택 전략은 종종 환경(environment) 수준에서 학습을 할당하거나 국소적인 보상(reward) 기반 신호에 우선순위를 두며, 프롬프트(prompt) 그룹 선택 시 환경 간 현재 롤아웃(rollout) 사이의 관계를 명시적으로 고려하지 않습니다. 한편, 환경마다 학습되는 속도가 다르기 때문에 배치(batch) 내에 전체 실패 및 전체 성공 롤아웃 그룹이 공존할 수 있으며, 이로 인해 해당 데이터에는 그룹 상대적 보상 신호가 남지 않게 됩니다. 이러한 두 가지 과제는 다중 환경 강화학습(RL)에서 스칼라 보상에만 의존하는 것의 한계를 부각합니다. 즉, 스칼라 보상은 환경 간 관계에 대한 제한적인 정보만 제공하며, 보상이 동일할 때는 그룹 내 보상 대조를 제공하지 못합니다. 이는 학습을 유도하기 위해 롤아웃 행동을 기술하는 루브릭(rubric)과 같은 더 풍부한 텍스트 피드백의 필요성을 동기부여합니다. 보상으로서의 루브릭 활용을 넘어, 본 연구는 온라인 데이터 선택과 정책 감독을 모두 유도하도록 루브릭을 재목적화합니다. LLM 판별기(judge)는 환경 전반에 걸쳐 공유되는 사전 정의된 루브릭 어휘를 사용하여 각 롤아웃에 태그를 지정합니다. 생성된 프로필은 이미 선택된 데이터와의 중복을 제한하면서 혼합 환경 배치의 전반적인 행동 구성과 일치하는 데이터 선택을 안내합니다. 사용 가능한 긍정적 루브릭(바람직한 행동 설명)은 온-정책(on-policy) 자기 증류 교사 모델(model)을 위한 특권적 맥락(privileged context)을 제공하여 추가적인 토큰(token) 수준의 감독을 공급하는 반면, 부정적 루브릭(원치 않는 행동 설명)은 이후의 롤아웃 생성이 반복되는 실패 모드에서 벗어나도록 유도합니다. 이러한 구성 요소들이 결합하여 RISED를 형성합니다. 여러 모델 백본에 걸쳐 RISED는 환경 전반에서 가장 높은 평균 통과율을 달성하며 모든 개별 환경에서 1위 또는 2위를 기록합니다. RISED에 대한 루브릭 기반 분석은 이러한 성능 향상에 수반되는 행동 변화를 추가로 규명할 수 있습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.