🤖 AI

dtControl2+ $\varepsilon$ : Trading Optimality for Explainability in MDPs via Decision Trees

이 논문은 최적성( $\varepsilon$ )을 조절 가능한 수준으로 양보하는 대신 설명 가능성을 향상시킴으로써 마르코프 결정 과정(Markov decision processes)을 위한 현저히 더 작고 인간이 이해하기 쉬운 의사결정 나무 컨트롤러를 생성하는, 최첨단 도구인 dtControl2의 확장판인 dtControl2+ $\varepsilon$ 을 소개한다.

원저자: Tereza Kinská, Jan Křetínský, Tobias Meggendorfer, Sabine Rieder, Maximilian Weininger

게시일 2026-07-29

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Tereza Kinská, Jan Křetínský, Tobias Meggendorfer, Sabine Rieder, Maximilian Weininger

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

로봇에게 미로를 탐색하는 법을 가르치려 한다고 상상해 보세요. 컴퓨터 과학에서는 이를 "컨트롤러 합성(controller synthesis)"이라고 부릅니다. 당신은 로봇에게 일련의 규칙과 목표를 주고, 컴퓨터 프로그램은 그곳에 도달하기 위한 완벽한 움직임을 찾아냅니다. 하지만 여기 함정이 있습니다. 복잡한 미로의 경우, 컴퓨터는 종종 거대하고 무질서한 지침 목록을 내놓습니다. 로봇이 발을 디딜 수 있는 모든 개별 칸마다 하나씩의 지침을 만드는 식이죠. 이는 마치 백만 페이지에 달하는 요리책과 같아서, 각 페이지마다 특정 찰나의 순간에 대해 "왼쪽으로 돌아라" 또는 "오른쪽으로 돌아라"라고만 적혀 있는 것과 같습니다. 이 목록은 수학적으로는 완벽할지 모르지만, 인간이 읽거나 이해하는 것은 불가능합니다. 만약 로봇이 충돌했을 때, 아무도 그 거대한 목록을 보며 "아, 빨간 벽 때문에 당황해서 왼쪽으로 돌았구나"라고 말할 수 없습니다. 우리는 이 지침들이 거대한 스프레드시트가 아니라 명확한 지도처럼 짧고, 단순하며, 설명 가능하기를 원합니다.

여기에서 "의사결정 나무(decision trees)"가 등장합니다. 의사결정 나무를 플로우차트나 "스무 고개" 게임이라고 생각해 보세요. 거대한 목록 대신, "만약 벽이 왼쪽에 있다면 오른쪽으로 가고, 그렇지 않으면 직진하라"와 같은 단순한 구조를 갖게 됩니다. 이러한 방식은 인간이 이해하기 훨씬 쉽습니다. 하지만 로봇이 까다로운 상황이나 희귀한 "코너 케이스(corner cases)"에 직면하면, 이 나무조차 너무 크고 복잡해질 수 있습니다. 연구자들이 던지는 핵심 질문은 이것입니다. "성능 저하 없이 이 나무를 더 작고 단순하게 만들 수 있을까?" 그 답은 "엡실론-최적성(epsilon-optimality)"이라는 개념에 있습니다. 로봇에게 "100% 완벽할 필요는 없어. 99.9%만 완벽해도 돼"라고 말한다고 상상해 보세요. 이 아주 작은 허용된 불완전함은 로봇(그리고 컴퓨터)이 사소하고 발생 가능성이 낮은 세부 사항들을 무시할 수 있는 자유를 주어, 여전히 안전하게 임무를 수행하면서도 훨씬 더 짧고 깔고 깔끔한 지침 세트를 만들어냅니다.

"dtControl 2+ε: MDP를 통한 결정 나무를 이용한 최적성과 설명 가능성의 트레이드오프"라는 논문은 정확히 이 일을 수행하는 dtControl 2+ε라는 새로운 도구를 소개합니다. 마르코프 결정 과정(Markov Decision Processes, 미끄러운 바닥에서 로봇이 미끄러질 수 있는 것처럼 무작위성이 있는 시스템을 설명하는 멋진 수학적 방식)을 다루는 연구자들은, 복잡하고 완벽한 컨트롤러를 가져와서 이를 아주 작은, 인간이 읽을 수 있는 결정 나무로 축소하는 시스템을 구축했습니다. 그들은 아주 작은, 통제된 양의 오차( $\epsilon$ )를 허용함으로써 이 작업을 수행합니다.

그들의 마법이 작동하는 방식은 다음과 같습니다. 로봇의 모든 움직임을 설명하려고 노력하는 대신, 이 도구는 지도를 보고 "어떤 움직임이 실제로 중요한가?"를 묻습니다. 로봇이 거의 절대 가지 않을 장소에 있거나, 어떤 움직임을 취하든 결과가 동일한 곳에 있다면, 도구는 "그 부분에 대한 설명은 건너뛰자"라고 말합니다. 이 도구는 컨트롤러의 "본질"로 정수를 추출합니다. 예를 들어, 언덕 위의 로봇을 대상으로 한 테스트에서 완벽한 컨트롤러는 수십 개의 복잡한 규칙을 가지고 있었습니다. 하지만 엡실론( $\epsilon$ )을 0.001만큼 허용한 이 새로운 도구는 지침을 단 5개의 노드(결정 지점)로 줄였습니다. 그 결과 나온 규칙은 매우 아름답고 단순했습니다: "위로 올라가서, 오른쪽 끝으로 가서, 내려가라." 이는 모든 미세한 시나리오에서 수학적으로 완벽하지는 않았지만, 차이가 무시할 수 있을 정도로 미미했기에 인간이 몇 초 만에 이해할 수 있는 수준이었습니다.

연구팀은 이 도구를 다른 최첨단 방법들과 비교 테스트했으며, 그 결과 압도적인 개선을 확인했습니다. 많은 경우, 그들의 도구는 경쟁 모델보다 수십 배(orders of magnitude) 더 작은 결정 나무를 만들어냈습니다. 실제로 그들이 실행한 테스트 케이스 중 거의 절반에 가까운 사례에서, $\epsilon = 10^{-2}$ (0.01)의 작은 오차를 허용하자 전체 컨트롤러를 단 하나의 노드로 축소할 수 있었습니다. 이는 로봇이 단 하나의 주요 행동을 선택하고, 만약 그 행동이 불가능하다면 다른 사용 가능한 움직임을 무작위로 선택하기만 해도, 여전히 완벽하고 복잡한 전략만큼이나 성능이 좋다는 것을 의미합니다. 이는 이전의 도구들이 전혀 놓쳤던 사실입니다.

연구자들은 단순히 추측한 것이 아님을 강조하기 위해, 강력한 모델 체커(시스템이 제대로 작동하는지 수학적으로 검증하는 도구)를 사용하여 단순화된 모든 나무를 재검증했습니다. 그들은 이러한 공격적인 단순화에도 불구하고 로봇의 성능이 허용된 안전 한계 아래로 떨어지지 않는다는 것을 증명했습니다. 또한, 그들의 도구가 목적지에 도달하는 것뿐만 아니라 위험을 피하거나 보상을 수집하는 등 다양한 유형의 목표에서도 작동함을 보여주었습니다.

요약하자면, 이 논문은 수학적 완벽함에 대한 아주 작은 통제된 양을 희생하여 인간의 이해도를 크게 높이는 방법을 제시합니다. 컴퓨터가 모든 사소한 세부 사항까지 설명할 필요가 없음을 인정하게 함으로써, 연구자들은 안전하고 효과적이면서도 엽서 한 장에 들어갈 만큼 작고, 인간이 친구에게 설명할 수 있을 만큼 단순한 컨트롤러를 만들어냈습니다. 이는 혼란스러운 백만 페이지짜리 지침서를 명확한 3단계 가이드로 바꾸어 놓았습니다.

기술 요약: dtControl2+ε: 설명 가능성을 위한 의사결정 나무 기반의 MDP 최적 제어

문제 정의

마르코프 결정 과정(MDP)에 대한 컨트롤러 합성(Controller synthesis)은 종종 거대하고 구조화되지 않은 상태-행동 테이블로 표현되는 최적 컨트롤러를 생성합니다. 이러한 테이블은 수학적으로는 정밀하지만, 자원이 제한된 장치에 구현하기에는 비실용적이며, 설명 가능성이 부족하여 검증 및 인증을 저해합니다. dtControl2와 같은 기존 도구들은 이러한 컨트롤러를 의사결정 나무(Decision Trees, DT)로 표현하여 해석력을 높이려고 시도합니다. 그러나 시스템이 크거나 예외 케이스(corner cases)가 많은 경우, 이러한 DT조차도 인간이 이해하기에는 너무 복민 복잡해질 수 있습니다.

DT 크기를 줄이는 것은 매우 까다로운 문제입니다. 단 하나의 중요한 결정이라도 제거하면 컨트롤러가 부정확해질 수 있기 때문입니다. 더욱이, 많은 확장 가능한 합성 방법들은 $\epsilon$ -최적(최적값의 $\epsilon$ 이내의 성능을 갖는) 컨트롤러만을 제공하는 경우가 많지만, 기존의 DT 구축 도구들은 일반적으로 정확한( $\epsilon=0$ ) 표현을 목표로 하므로, 단순화를 위해 허용된 불정밀성(imprecision)을 활용하지 못한다는 한계가 있습니다.

방법론

본 논문은 " $\epsilon$ " 기능을 도입하여 기존의 dtControl2를 확장한 dtControl2+ $\epsilon$ 를 제시합니다. 핵심 워크플로우는 확률적 모델 체커인 Storm과 긴밀하게 통합되어, 결과물이 $\epsilon$ -최적임을 보장하면서도 더 작고 설명 가능한 DT를 구축합니다.

방법론은 다음 세 단계로 진행됩니다:

1. 모델 풀이 및 데이터셋 구축

도구는 결정론적 최적 컨트롤러에서 시작하는 대신, 허용적(permissive)(상태를 허용된 행동의 집합으로 매핑) 또는 결합된(combined)(허용적 행동을 도달 가능한 상태로 제한) 초기 데이터셋을 생성합니다.

허용적 전략 (Permissive Strategies): 도구는 최적이거나 동일한 값을 산출하는 행동들을 식별하여, DT가 상태들을 "통합(unify)"할 수 있도록 합니다.
축소 휴리스틱 (Reduction Heuristics): DT를 학습하기 전에, 도구는 특정 행동의 선택이 결과에 영향을 미치지 않거나 발생하는 오차가 $\epsilon$ $ϵ$ 이내인 상태들을 식별하고 제거합니다. 주요 축소 기법은 다음과 같습니다:
- AllOpt: 사용 가능한 모든 행동이 최적인 상태를 제거합니다.
- Agency: 최선의 결과와 최악의 결과 사이의 차이가 $\epsilon$ 보다 작은 상태를 제거합니다.
- Dominance: 선택한 행동과 관계없이 다른 상태로부터 거의 확실하게 도달되는 상태를 제거합니다.
- Unreach: 일관된 컨트롤러 하에서 초기 상태로부터 도달 불가능한 상태를 제거합니다.

2. 의사결정 나무 학습

도구는 표준적인 휴리스틱 기반 DT 구축 알고리즘(Algorithm 1)의 수정된 버전을 사용하며, 다음과 같은 몇 가지 향상된 기능을 포함합니다:

술어 추출 (Predicate Extraction): 고수준 모델 기술(예: PRISM 언어의 전이 가드)로부터 관련 술어를 자동으로 추출하여, 기존 도구들의 반자동 템플릿 방식보다 개선되었습니다.
불순도 측정 (Impurity Measures): 불순도 계산에 모델 특화된 가중치를 도입합니다. 균등한 가중치 대신 다음을 사용합니다:
- Imp_Simulation: 상태를 방문 빈도에 따라 가중치를 부여합니다 (단, $\epsilon$ -최적성을 보장하기 위한 안전 하한선을 둡).
- Imp_Agency: 상태를 그들의 에이전시(잠재적 오차)에 따라 가중치를 부여합니다.
- Imp_CoE (Cost of Error): 해당 상태에서 최악의 행동을 선택했을 때의 영향력에 따라 가중치를 부여합니다.
검증을 동반한 공격적 휴리스틱 (Aggressive Heuristics with Verification): 도구는 조기 종료(Early-Stopping)(불순도가 임계값 미만일 때 분할을 중단) 및 탐욕적 가지치기(Greedy Pruning)(서브트리를 축소)를 채택합니다. 건전성(soundness)을 해칠 위험이 있는 기존의 "공격적" 접근 방식과 달리, dtControl2+ $\epsilon$ 은 DT 구축 후 Storm을 사용하여 $\epsilon$ -최적성을 검증합니다. 만약 정밀도 제약 조건이 위반되면, 도구는 휴리스틱을 완화하고 다시 시도합니다.

3. 검증 루프

Storm과의 긴밀한 결합을 통한 사후 구축 검증은 이 도구의 독특한 특징입니다. 도구는 생성된 DT의 정밀도를 확인합니다. 만약 최적값으로부터의 편차가 $\epsilon$ 을 초과하면, 도구는 백트래킹하여 휴리스틱의 공격성을 줄임으로써(예: 중단 임계값을 높이거나 가지치기를 비활성화) 최종 출력이 반드시 $\epsilon$ -최적임을 보장합니다.

주요 기여

dtControl2+ $\epsilon$ 도구: $\epsilon$ 이라는 허용된 불정밀성을 활용하여 더 작은 DT를 구축하도록 dtControl2를 확장한 독립적인 도구입니다.
안전한 vs 공격적 휴리스틱: "안전한" 축소(정의에 의해 $\epsilon$ -최적성을 보존함)와 "검증을 통해 검증되는 공격적" 휴리스틱을 명확히 구분하는 프레임워크를 제공합니다.
자동 술어 추출: 모델의 전이 가드로부터 의사결정 술어를 직접 유도하는 방법을 통해, 술격 선택에 필요한 수동 도메인 전문 지식의 필요성을 제거했습니다.
다양한 목적 지원: 표준적인 목적(도달 가능성, 안전성, 도달-회피, 보상 기반)을 다루며, 메모리 기반 컨트롤러를 처리함으로써 독특하게 선형 시간 논리(LTL) 속성을 지원합니다.

결과

저자들은 38개의 벤치마크(최대 500,000개의 상태를 가진 PRISM 모델 포함)를 대상으로 dtControl2+ $\epsilon$ 을 dtControl2, dtPaynt, dtNESt, 그리고 CAV15 방식의 재구현 모델과 비교 평가했습니다.

크기 감소: $\epsilon=0$ 인 정확한 표현의 경우에도, dtControl2+ $\epsilon$ 은 개선된 초기 데이터셋과 안전한 휴리스틱 덕분에 dtControl2보다 수십 배 더 작은 DT를 생성합니다.
$\epsilon$ 의 영향: $\epsilon = 10^{-2}$ 를 허용했을 때, 이 도구는 거의 절반의 벤치마크에서 단일 노드 DT를 생성하였으며, 이는 단일 행동(균등 무작위 폴백 포함)만으로도 $\epsilon$ -최적성을 위해 충분할 수 있음을 보여줍니다.
비교:
- vs. dtControl2: dtControl2+ $\epsilon$ 은 일관되게 더 작은 트리를 생성합니다.
- vs. dtPaynt: dtPaynt는 대부분의 벤치마크에서 타임아웃이 발생했으며, 성공한 경우에도 더 큰 트리를 생성했습니다.
- vs. dtNESt: dtNESt는 $\epsilon=0$ 에서 강력한 경쟁자이지만, dtControl2+ $\epsilon$ 은 38개 중 23개 벤치마크에서 dtNESt보다 최대 절반 크기의 트리를 생성하며, 10개에서는 한 자릿수 이상의 차이를 보였습니다. 특히 dtNESt는 $\epsilon > 0$ 일 때 실패하거나 더 큰 트리를 생성하는 경우가 많은 반면, dtControl2+ $\epsilon$ 은 불정밀성을 활용하는 데 탁월합니다.
확장성: 도구는 20분 타임아웃 내에 단 하나의 벤치마크를 제외한 모든 벤치마크를 해결하여, 대규모의 복잡한 모델에서도 실행 가능함을 입증했습니다.

의의

본 논문은 dtControl2+ $\epsilon$ 이 설명 가능한 컨트롤러 합성 분야에서 상당한 진보를 이루었다고 주장합니다. 제어 가능한 수준의 최적성을 크기와 맞교환함으로써, 이 도구는 이전에는 해석하기 너무 복합했던, 인간이 이해할 수 있는 컨트롤러를 생성할 수 있게 합니다. 구조적 통찰(예: $\epsilon$ -최적성을 위해 단일 규칙이 충분하다는 점을 식별)을 자동으로 도출하고 LTL 속성을 지원하는 능력은 기존 도구들과 차별화됩니다. 저자들은 자신들의 접근 방식이 기존의 휴리스틱 기반 가지치기 방법들이 정답성을 해칠 수 있는 것과 달리, $\epsilon$ -최적성을 보장한다는 점을 강조합니다.