What type of inference is planning?

Authors: miguel  lázaro
gredilla  li
yang  ku
kevin p murphy
dileep  george
google  deepmind
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 01:55:17

Abstract: Multiple types of inference are available for probabilistic graphical models, e.g., marginal, maximum-a-posteriori, and even marginal maximum-a-posteriori. Which one do researchers mean when they talk about ``planning as inference''? There is no consistency in the literature, different types are used, and their ability to do planning is further entangled with specific approximations or additional constraints. In this work we use the variational framework to show that, just like all commonly used types of inference correspond to different weightings of the entropy terms in the variational problem, planning corresponds _exactly_ to a _different_ set of weights. This means that all the tricks of variational inference are readily applicable to planning. We develop an analogue of loopy belief propagation that allows us to perform approximate planning in factored-state Markov decisions processes without incurring intractability due to the exponentially large state space. The variational perspective shows that the previous types of inference for planning are only adequate in environments with low stochasticity, and allows us to characterize each type by its own merits, disentangling the type of inference from the additional approximations that its practical use requires. We validate these results empirically on synthetic MDPs and tasks posed in the International Planning Competition.

Main paper: 
 introduction: 
 There are many kinds of probabilistic inference, such as marginal, maximum-a-posteriori (MAP), or marginal MAP (MMAP) that are used in the planning as inference literature (Attias, 2003; Levine, 2018; Cui et al., 2019; Palmieri et al., 2022; Wu and Khardon, 2022) . In this work we show that planning is a distinct type of inference, and that under stochastic dynamics does not correspond exactly with any of the above methods. Furthermore, we show how to rank the above methods in terms of quality as it pertains to planning.Our approach is based on a variational perspective, which allows direct comparison between different inference types, and to develop analogues of existing approximate inference algorithms for this "planning inference" task. Given the "flat" Markov Decision Process (MDP) from Fig 1 [Left] , we show that planning inference provides the same (exact) results as value iteration. Using an analogue of loopy belief propagation (LBP), we show how to apply approximate planning inference to the factored MDP in Fig. 1 [Right], which has an exponentially large state space, and for which exact solutions are no longer tractable. Under moderate stochasticity in the dynamics, we show that this approximate planning inference might be superior to other more established types of inference. 
markov decision processes (mdps) and notation: 
 A finite-horizon Markov decision process (MDP) is a tuple (X , A, p(x 1 ), P, R, T ), where X is the state space, A an action space with cardinality N a , p(x 1 ) the starting state distribution, P the 38th Conference on Neural Information Processing Systems (NeurIPS 2024).< l a t e x i t s h a 1 _ b a s e 6 4 = " d f V + f a S O 9 z t a X 2 O B e b M 7 u n 4 O r d U = " > A A A B 8 3 i c d V D L T g J B E O z F F + I L 9 e h l I j G B y 2 Y X Q e B G 9 O I R E w E T W M n s M M C E 2 U d m Z o 1 k w 2 9 4 8 a A x X v 0 Z b / 6 N s 7 A m a r S S T i p V 3 e n u c k P O p L K s D y O z s r q 2 v p H d z G 1 t 7 + z u 5 f c P O j K I B K F t E v B A 3 L h Y U s 5 8 2 l Z M c X o T C o o 9 l 9 O u O 7 1 I / O 4 d F Z I F / r W a h d T x 8 N h n I 0 a w 0 l K / V b w f 2 L d x 0 S 7 N S 4 N 8 w T I b d a t e q y L L t B Z I S L l S P W 0 g O 1 U K k K I 1 y L / 3 h w G J P O o r w r G U P d s K l R N j o R j h d J 7 r R 5 K G m E z x m P Y 0 9 b F H p R M v b p 6 j E 6 0 M 0 S g Q u n y F F u r 3 i R h 7 U s 4 8 V 3 d 6 W E 3 k b y 8 R / / J 6 k R r V n Z j 5 Y a S o T 5 a L R h F H K k B J A G j I B C W K z z T B R D B 9 K y I T L D B R O q a c D u H r U / Q / 6 Z R N + 8 y s X F U K z f M 0 j i w c w T E U w Y Y a N O E S W t A G A i E 8 w B M 8 G 5 H x a L w Y r 8 v W j J H O H M I P G G + f h N W Q u A = = < / l a t e x i t > P (x (1) 1 )< l a t e x i t s h a 1 _ b a s e 6 4 = " E 1 r i 4 K X B 8 p 6 k 3 r L x M U h K T F S Y e v A = " > A A A B 8 3 i c d V D L T g J B E O z F F + I L 9 e h l I j G B y 2 Y X Q e B G 9 O I R E w E T W M n s M M C E 2 U d m Z o 1 k w 2 9 4 8 a A x X v 0 Z b / 6 N s 7 A m a r S S T i p V 3 e n u c k P O p L K s D y O z s r q 2 v p H d z G 1 t 7 + z u 5 f c P O j K I B K F t E v B A 3 L h Y U s 5 8 2 l Z M c X o T C o o 9 l 9 O u O 7 1 I / O 4 d F Z I F / r W a h d T x 8 N h n I 0 a w 0 l K / V b w f 2 L d x s V y a l w b 5 g m U 2 6 l a 9 V k W W a S 2 Q k H K l e t p A d q o U I E V r k H / v D w M S e d R X h G M p e 7 Y V K i f G Q j H C 6 T z X j y Q N M Z n i M e 1 p 6 m O P S i d e 3 D x H J 1 o Z o l E g d P k K L d T v E z H 2 p J x 5 r u 7 0 s J r I 3 1 4 i / u X 1 I j W q O z H z w 0 h R n y w X j S K O V I C S A N C Q C U o U n 2 m C i W D 6 V k Q m W G C i d E w 5 H c L X p + h / 0 i m b 9 p l Z u a o U m u d p H F k 4 g m M o g g 0 1 a M I l t K A N B E J 4 g C d 4 N i L j 0 X g x X p e t G S O d O Y Q f M N 4 + A Y Z c k L k = < / l a t e x i t >(2) 1 )< l a t e x i t s h a 1 _ b a s e 6 4 = " u U E G / o 2 n a F P w 2 6 e m o h t / T b 2 i q b k = " > A A A B 8 3 i c d V D L S s N A F J 3 U V 6 2 v q k s 3 g 0 V o N y H p w 7 a 7 o h u X F e w D 2 l g m 0 0 k 7 d D I J M x O x h P 6 G G x e K u P V n 3 P k 3 T t o I K n r g w u G c e 7 n 3 H j d k V C r L + j A y a + s b m 1 v Z 7 d z O 7 t 7 + Q f 7 w q C u D S G D S w Q E L R N 9 F k j D K S U d R x U g / F A T 5 L i M 9 d 3 a Z + L 0 7 I i Q N + I 2 a h 8 T x 0 Y R T j 2 K k t D R s F + 9 H 9 m 1 c r J Q W p V G + Y J n N h t W o 1 6 B l W k s k p F y t V Z r Q T p U C S N E e 5 d + H 4 w B H P u E K M y T l w L Z C 5 c R I K I o Z W e S G k S Q h w j M 0 I Q N N O f K J d O L l z Q t 4 p p U x 9 A K h i y u 4 V L 9 P x M i X c u 6 7 u t N H a i p / e 4 n 4 l z e I l N d w Y s r D S B G O V 4 u 8 i E E V w C Q A O K a C Y M X m m i A s q L 4 V 4 i k S C C s d U 0 6 H 8 P U p / J 9 0 y 6 Z 9 b l a v q 4 X W R R p H F p y A U 1 A E N q i D F r g C b d A B G I T g A T y B Z y M y H o 0 X 4 3 X V m j H S m W P w A 8 b b J 4 f j k L o = < / l a t e x i t > P (x(3) 1 )< l a t e x i t s h a 1 _ b a s e 6 4 = " S g g l X f G o / V w q e 6 a X B g q H G p S v Z 1 Y = " > A A A B 8 3 i c d V B N T 8 J A E N 3 i F + I X 6 t H L R m I C l 6 b F I n A j e v G I i Y A J V L J d t r B h u 2 1 2 t 0 b S 8 D e 8 e N A Y r / 4 Z b / 4 b t 1 A T N f q S S V 7 e m 8 n M P C 9 i V C r L + j B y K 6 t r 6 x v 5 z c L W 9 s 7 u X n H / o C v D W G D S w S E L x Y 2 H J G G U k 4 6 i i p G b S B A U e I z 0 v O l F 6 v f u i J A 0 5 N d q F h E 3 Q G N O f Y q R 0 t K g X b 4 f 2 r d J 2 a n M K 8 N i y T K b D a t R r 0 H L t B Z I S d W p n T a h n S k l k K E 9 L L 4 P R i G O A 8 I V Z k j K v m 1 F y k 2 Q U B Q z M i 8 M Y k k i h K d o T P q a c h Q Q 6 S a L m + f w R C s j 6 I d C F 1 d w o X 6 f S F A g 5 S z w d G e A 1 E T + 9 l L x L 6 8 f K 7 / h J p R H s S I c L x f 5 M Y M q h G k A c E Q F w Y r N N E F Y U H 0 r x B M k E F Y 6 p o I O 4 e t T + D / p V k 3 7 z H S u n F L r P I s j D 4 7 A M S g D G 9 R B C 1 y C N u g A D C L w A J 7 A s x E b j 8 a L 8 b p s z R n Z z C H 4 A e P t E 4 l q k L s = < / l a t e x i t > P (x (4) 1 )< l a t e x i t s h a 1 _ b a s e 6 4 = " 8 R c n + l i G g A d E f + a C n W m N B P M 2 2 h w = " > A A A B 8 H i c b V B N S w M x E J 2 t X 7 V + V T 1 6 C R a h X s q u F P V Y 9 O K x g v 2 Q d i 3 Z N N u G J t k l y Y p l 6 a / w 4 k E R r / 4 c b / 4 b 0 3 Y P 2 v p g 4 P H e D D P z g p g z b V z 3 2 8 m t r K 6 t b + Q 3 C 1 v b O 7 t 7 x f 2 D p o 4 S R W i D R D x S 7 Q B r y p m k D c M M p + 1 Y U S w C T l v B 6 H r q t x 6 p 0 i y S d 2 Y c U 1 / g g W Q h I 9 h Y 6 f 6 p 5 z 2 k Z e 9 0 0 i u W 3 I o 7 A 1 o m X k Z K k K H e K 3 5 1 + x F J B J W G c K x 1 x 3 N j 4 6 d Y G U Y 4 n R S 6 i a Y x J i M 8 o B 1 L J R Z U + + n s 4 A k 6 s U o f h Z G y J Q 2 a q b 8 n U i y 0 H o v A d g p s h n r R m 4 r / e Z 3 E h J d + y m S c G C r J f F G Y c G Q i N P 0 e 9 Z m i x P C x J Z g o Z m 9 F Z I g V J s Z m V L A h e I s v L 5 P m W c U 7 r 1 R v q 6 X a V R Z H H o 7 g G M r g w Q X U 4 A b q 0 A A C A p 7 h F d 4 c 5 b w 4 7 8 7 H v D X n Z D O H 8 A f O 5 w / C r o + 9 < / l a t e x i t >x (1) 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " e s 0 F a W k g S 5 w Q x r N a v q r i H N Z L Q q 4 = " > A A A B 8 H i c b V B N S w M x E J 3 1 s 9 a v q k c v w S L U S 9 k t R T 0 W v X i s Y D + k X U s 2 z b a h S X Z J s m J Z + i u 8 e F D E q z / H m / / G t N 2 D t j 4 Y e L w 3 w 8 y 8 I O Z M G 9 f 9 d l Z W 1 9 Y 3 N n N b + e 2 d 3 b 3 9 w s F h U 0 e J I r R B I h 6 p d o A 1 5 U z S h m G G 0 3 a s K B Y B p 6 1 g d D 3 1 W 4 9 U a R b J O z O O q S / w Q L K Q E W y s d P / U 8 x 7 S U u V s 0 i s U 3 b I 7 A 1 o m X k a K k K H e K 3 x 1 + x F J B J W G c K x 1 x 3 N j 4 6 d Y G U Y 4 n e S 7 i a Y x J i M 8 o B 1 L J R Z U + + n s 4 A k 6 t U o f h Z G y J Q 2 a q b 8 n U i y 0 H o v A d g p s h n r R m 4 r / e Z 3 E h J d + y m S c G C r J f F G Y c G Q i N P 0 e 9 Z m i x P C x J Z g o Z m 9 F Z I g V J s Z m l L c h e I s v L 5 N m p e y d l 6 u 3 1 W L t K o s j B 8 d w A i X w 4 A J q c A N 1 a A A B A c / w C m + O c l 6 c d + d j 3 r r i Z D N H 8 A f O 5 w / E N I + + < / l a t e x i t > x(2) 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " j T y e 4 n K t r s 1 4 7 Z y P i I b g p 5 4 6 W d k = " > A A A B 8 H i c b V B N S w M x E J 3 1 s 9 a v q k c v w S L U S 9 n V o h 6 L X j x W s B / S r i W b Z t v Q J L s k W b E s / R V e P C j i 1 Z / j z X 9 j 2 u 5 B W x 8 M P N 6 b Y W Z e E H O m j e t + O 0 v L K 6 t r 6 7 m N / O b W 9 s 5 u Y W + / o a N E E V o n E Y 9 U K 8 C a c i Z p 3 T D D a S t W F I u A 0 2 Y w v J 7 4 z U e q N I v k n R n F 1 B e 4 L 1 n I C D Z W u n / q e g 9 p 6 e x k 3 C 0 U 3 b I 7 B V o k X k a K k K H W L X x 1 e h F J B J W G c K x 1 2 3 N j 4 6 d Y G U Y 4 H e c 7 i a Y x J k P c p 2 1 L J R Z U + + n 0 4 D E 6 t k o P h Z G y J Q 2 a q r 8 n U i y 0 H o n A d g p s B n r e m 4 j / e e 3 E h J d + y m S c G C r J b F G Y c G Q i N P k e 9 Z i i x P C R J Z g o Z m 9 F Z I A V J s Z m l L c h e P M v L 5 L G a d k 7 L 1 d u K 8 X q V R Z H D g 7 h C E r g w Q V U 4 Q Z q U A c C A p 7 h F d 4 c 5 b w 4 7 8 7 H r H X J y W Y O 4 A + c z x / F u o + / < / l a t e x i t > x(3) 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " 1 d n 1 A D U o K b R p i w + s P j H I L E e T r Z Q = " > A A A B 8 H i c b V B N S w M x E J 2 t X 7 V + V T 1 6 C R a h X s q u F P V Y 9 O K x g v 2 Q d i 3 Z N N u G J t k l y Y p l 6 a / w 4 k E R r / 4 c b / 4 b 0 3 Y P 2 v p g 4 P H e D D P z g p g z b V z 3 2 8 m t r K 6 t b + Q 3 C 1 v b O 7 t 7 x f 2 D p o 4 S R W i D R D x S 7 Q B r y p m k D c M M p + 1 Y U S w C T l v B 6 H r q t x 6 p 0 i y S d 2 Y c U 1 / g g W Q h I 9 h Y 6 f 6 p 5 z 2 k 5 e r p p F c s u R V 3 B r R M v I y U I E O 9 V / z q 9 i O S C C o N 4 V j r j u f G x k + x M o x w O i l 0 E 0 1 j T E Z 4 Q D u W S i y o 9 t P Z w R N 0 Y p U + C i N l S x o 0 U 3 9 P p F h o P R a B 7 R T Y D P W i N x X / 8 z q J C S / 9 l M k 4 M V S S + a I w 4 c h E a P o 9 6 j N F i e F j S z B R z N 6 K y B A r T I z N q G B D 8 B Z f X i b N s 4 p 3 X q n e V k u 1 q y y O P B z B M Z T B g w u o w Q 3 U o Q E E B D z D K 7 w 5 y n l x 3 p 2 P e W v O y W Y O 4 Q + c z x / H Q I / A < / l a t e x i t > x (4) 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " 0 f l w I Y z z a c t o B 6 K T o L f R q R c N a + 0 = " > A A A B + 3 i c b V B N S 8 N A E N 3 4 W e t X r E c v i 0 W o l 5 J I U Y 9 F L x 4 r 2 A 9 o Y 9 h s t + 3 S z S b s T q Q l 5 K 9 4 8 a C I V / + I N / + N 2 z Y H b X 0 w 8 H h v h p l 5 Q S y 4 B s f 5 t t b W N z a 3 t g s 7 x d 2 9 / Y N D + 6 j U 0 l G i K G v S S E S q E x D N B J e s C R w E 6 8 S K k T A Q r B 2 M b 2 d + + 4 k p z S P 5 A N O Y e S E Z S j 7 g l I C R f L s 0 8 d 3 H t A d s A m l M s o p 7 n v l 2 2 a k 6 c + B V 4 u a k j H I 0 f P u r 1 4 9 o E j I J V B C t u 6 4 T g 5 c S B Z w K l h V 7 i W Y x o W M y Z F 1 D J Q m Z 9 t L 5 7 R k + M 0 o f D y J l S g K e q 7 8 n U h J q P Q 0 D 0 x k S G O l l b y b + 5 3 U T G F x 7 K Z d x A k z S x a J B I j B E e B Y E 7 n P F K I i p I Y Q q b m 7 F d E Q U o W D i K p o Q 3 O W X V 0 n r o u p e V m v 3 t X L 9 J o + j g E 7 Q K a o g F 1 2 h O r p D D d R E F E 3 Q M 3 p F b 1 Z m v V j v 1 s e i d c 3 K Z 4 7 R H 1 i f P 6 a R l D I = < / l a t e x i t > x pa(1) 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " O 2 S T b u f U u W x b z J U w r l k 5 Z t W D h N 4 = " > A A A B + 3 i c b V B N S 8 N A E N 3 U r 1 q / Y j 1 6 C R a h X k p S i n o s e v F Y w X 5 A G 8 N m u 2 m X b j Z h d y I t I X / F i w d F v P p H v P l v 3 L Y 5 a O u D g c d 7 M 8 z M 8 2 P O F N j 2 t 1 H Y 2 N z a 3 i n u l v b 2 D w 6 P z O N y R 0 W J J L R N I h 7 J n o 8 V 5 U z Q N j D g t B d L i k O f 0 6 4 / u Z 3 7 3 S c q F Y v E A 8 x i 6 o Z 4 J F j A C A Y t e W Z 5 6 j m P 6 Q D o F N I Y Z 9 X 6 R e a Z F b t m L 2 C t E y c n F Z S j 5 Z l f g 2 F E k p A K I B w r 1 X f s G N w U S 2 C E 0 6 w 0 S B S N M Z n g E e 1 r K n B I l Z s u b s + s c 6 0 M r S C S u g R Y C / X 3 R I p D p W a h r z t D D G O 1 6 s 3 F / 7 x + A s G 1 m z I R J 0 A F W S 4 K E m 5 B Z M 2 D s I Z M U g J 8 p g k m k u l b L T L G E h P Q c Z V 0 C M 7 q y + u k U 6 8 5 l 7 X G f a P S v M n j K K J T d I a q y E F X q I n u U A u 1 E U F T 9 I x e 0 Z u R G S / G u / G x b C 0 Y + c w J + g P j 8 w e o F 5 Q z < / l a t e x i t > x pa(2) 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " H Y s 7 G n Q z Q s X U R o 7 7 Q g T w k H j f D L 8 = " > A A A B + 3 i c b V D L S s N A F J 3 U V 6 2 v W J d u B o t Q N y X R o i 6 L b l x W s A 9 o Y 5 h M J + 3 Q y Y O Z G 2 k J + R U 3 L h R x 6 4 + 4 8 2 + c t l l o 6 4 E L h 3 P u 5 d 5 7 v F h w B Z b 1 b R T W 1 j c 2 t 4 r b p Z 3 d v f 0 D 8 7 D c V l E i K W v R S E S y 6 x H F B A 9 Z C z g I 1 o 0 l I 4 E n W M c b 3 8 7 8 z h O T i k f h A 0 x j 5 g R k G H K f U w J a c s 3 y x L U f 0 z 6 w C a Q x y a o X Z 5 l r V q y a N Q d e J X Z O K i h H 0 z W / + o O I J g E L g Q q i V M + 2 Y n B S I o F T w b J S P 1 E s J n R M h q y n a U g C p p x 0 f n u G T 7 U y w H 4 k d Y W A 5 + r v i Z Q E S k 0 D T 3 c G B E Z q 2 Z u J / 3 m 9 B P x r J + V h n A A L 6 W K R n w g M E Z 4 F g Q d c M g p i q g m h k u t b M R 0 R S S j o u E o 6 B H v 5 5 V X S P q / Z l 7 X 6 f b 3 S u M n j K K J j d I K q y E Z X q I H u U B O 1 E E U T 9 I x e 0 Z u R G S / G u / G x a C 0 Y + c w R + g P j 8 w e p n Z Q 0 < / l a t e x i t > x pa(3) 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " h 9 / h G x Y J W j q j b C S 8 Q S J l 6 H R 8 O q k = " > A A A B + 3 i c b V B N S 8 N A E N 3 4 W e t X r E c v i 0 W o l 5 J I U Y 9 F L x 4 r 2 A 9 o Y 9 h s t + 3 S z S b s T q Q l 5 K 9 4 8 a C I V / + I N / + N 2 z Y H b X 0 w 8 H h v h p l 5 Q S y 4 B s f 5 t t b W N z a 3 t g s 7 x d 2 9 / Y N D + 6 j U 0 l G i K G v S S E S q E x D N B J e s C R w E 6 8 S K k T A Q r B 2 M b 2 d + + 4 k p z S P 5 A N O Y e S E Z S j 7 g l I C R f L s 0 8 d 3 H t A d s A m l M s k r t P P P t s l N 1 5 s C r x M 1 J G e V o + P Z X r x / R J G Q S q C B a d 1 0 n B i 8 l C j g V L C v 2 E s 1 i Q s d k y L q G S h I y 7 a X z 2 z N 8 Z p Q + H k T K l A Q 8 V 3 9 P p C T U e h o G p j M k M N L L 3 k z 8 z + s m M L j 2 U i 7 j B J i k i 0 W D R G C I 8 C w I 3 O e K U R B T Q w h V 3 N y K 6 Y g o Q s H E V T Q h u M s v r 5 L W R d W 9 r N b u a + X 6 T R 5 H A Z 2 g U 1 R B L r p C d X S H G q i J K J q g Z / S K 3 q z M e r H e r Y 9 F 6 5 q V z x y j P 7 A + f w C r I 5 Q 1 < / l a t e x i t >x pa(4) 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " V b t p 7 i K N W T d I s N 1 w X + s L 4 0 L x 0 Z g = " > A A A B + 3 i c b V D L S s N A F J 3 U V 6 2 v W J d u B o t Q N y W R + l g W 3 b i s Y B / Q x j C Z T t q h k w c z N 9 I S 8 i t u X C j i 1 h 9 x 5 9 8 4 b b P Q 1 g M X D u f c y 7 3 3 e L H g C i z r 2 y i s r W 9 s b h W 3 S z u 7 e / s H 5 m G 5 r a J E U t a i k Y h k 1 y O K C R 6 y F n A Q r B t L R g J P s I 4 3 v p 3 5 n S c m F Y / C B 5 j G z A n I M O Q + p w S 0 5 J r l i W s / p n 1 g E 0 h j k l U v z j L X r F g 1 a w 6 8 S u y c V F C O p m t + 9 Q c R T Q I W A h V E q Z 5 t x e C k R A K n g m W l f q J Y T O i Y D F l P 0 5 A E T D n p / P Y M n 2 p l g P 1 I 6 g o B z 9 X f E y k J l J o G n u 4 M C I z U s j c T / / N 6 C f j X T s r D O A E W 0 s U i P x E Y I j w L A g + 4 Z B T E V B N C J d e 3 Y j o i k l D Q c Z V 0 C P b y y 6 u k f V 6 z L 2 v 1 + 3 q l c Z P H U U T H 6 A R V k Y 2 u U A P d o S Z q I Y o m 6 B m 9 o j c j M 1 6 M d + N j 0 V o w 8 p k j 9 A f G 5 w + s q Z Q 2 < / l a t e x i t > x pa(5) 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " D s R 8 a x c N P B U w F X / j j T F K X e 1 S 8 W 4 = " > A A A B + 3 i c b V D L S s N A F J 3 U V 6 2 v W J d u B o t Q N y W R U l 0 W 3 b i s Y B / Q x j C Z T t q h k w c z N 9 I S 8 i t u X C j i 1 h 9 x 5 9 8 4 b b P Q 1 g M X D u f c y 7 3 3 e L H g C i z r 2 y h s b G 5 t 7 x R 3 S 3 v 7 B 4 d H 5 n G 5 o 6 J E U t a m k Y h k z y O K C R 6 y N n A Q r B d L R g J P s K 4 3 u Z 3 7 3 S c m F Y / C B 5 j F z A n I K O Q + p w S 0 5 J r l q W s / p g N g U 0 h j k l U b F 5 l r V q y a t Q B e J 3 Z O K i h H y z W / B s O I J g E L g Q q i V N + 2 Y n B S I o F T w b L S I F E s J n R C R q y v a U g C p p x 0 c X u G z 7 U y x H 4 k d Y W A F + r v i Z Q E S s 0 C T 3 c G B M Z q 1 Z u L / 3 n 9 B P x r J + V h n A A L 6 X K R n w g M E Z 4 H g Y d c M g p i p g m h k u t b M R 0 T S S j o u E o 6 B H v 1 5 X X S u a z Z j V r 9 v l 5 p 3 u R x F N E p O k N V Z K M r 1 E R 3 q I X a i K I p e k a v 6 M 3 I j B f j 3 f h Y t h a M f O Y E / Y H x + Q O u L 5 Q 3 < / l a t e x i t >x pa(6) 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " h t f i m + J 0 L H 1 s 7 4 A p L R / O y J O h 5 S k = " > A A A C D 3 i c b V D J S g N B E O 1 x j X E b 9 e i l M S g J S J gJ Q T 0 G v X i M Y B Z I 4 t D T 6 U m a 9 C x 0 1 0 j C O H / g x V / x 4 k E R r 1 6 9 + T d 2 l o M m P i h 4 v F d F V T 0 3 E l y B Z X 0 b S 8 s r q 2 v r m Y 3 s 5 t b 2 z q 6 5 t 1 9 X Y S w p q 9 F Q h L L p E s U E D 1 g N O A j W j C Q j v i t Y w x 1 c j f 3 G P Z O K h 8 E t j C L W 8 U k v 4 B 6 n B L T k m C f V / N A p 4 Q e c t F 0 P D 1 P H v k v a w I a Q R C T N 2 4 X 0 F B P H L j h m z i p a E + B F Y s 9 I D s 1 Q d c y v d j e k s c 8 C o I I o 1 b K t C D o J k c C p Y G m 2 H S s W E T o g P d b S N C A + U 5 1 k 8 k + K j 7 X S x V 4 o d Q W A J + r v i Y T 4 S o 1 8 V 3 f 6 B P p q 3 h u L / 3 m t G L y L T s K D K A Y W 0 O k i L x Y Y Q j w O B 3 e 5 Z B T E S B N C J d e 3 Y t o n k l D Q E W Z 1 C P b 8 y 4 u k X i r a Z 8 X y T T l X u Z z F k U G H 6 A j l k Y 3 O U Q V d o y q q I Y o e 0 T N 6 R W / G k / F i v B s f 0 9 Y l Y z Z z g P 7 A + P w B K M q a 2 Q = = < / l a t e x i t > P (x2|x pa(1) 1 , a1) < l a t e x i t s h a 1 _ b a s e 6 4 = " U m y 0 6 z 3 4 f x i k S j i 0 j Q h U o E I B 8 B s = " > A A A B 8 H i c b V B N S w M x E J 3 1 s 9 a v q k c v w S L U S 9 k t R T 0 W v X i s Y D + k X U s 2 z b a h S X Z J s m J Z + i u 8 e F D E q z / H m / / G t N 2 D t j 4 Y e L w 3 w 8 y 8 I O Z M G 9 f 9 d l Z W 1 9 Y 3 N n N b + e 2 d 3 b 3 9 w s F h U 0 e J I r R B I h 6 p d o A 1 5 U z S h m G G 0 3 a s K B Y B p 6 1 g d D 3 1 W 4 9 U a R b J O z O O q S / w Q L K Q E W y s d P / U q z y k J e 9 s 0 i s U 3 b I 7 A 1 o m X k a K k K H e K 3 x 1 + x F J B J W G c K x 1 x 3 N j 4 6 d Y G U Y 4 n e S 7 i a Y x J i M 8 o B 1 L J R Z U + + n s 4 A k 6 t U o f h Z G y J Q 2 a q b 8 n U i y 0 H o v A d g p s h n r R m 4 r / e Z 3 E h J d + y m S c G C r J f F G Y c G Q i N P 0 e 9 Z m i x P C x J Z g o Z m 9 F Z I g V J s Z m l L c h e I s v L 5 N m p e y d l 6 u 3 1 W L t K o s j B 8 d w A i X w 4 A J q c A N 1 a A A B A c / w C m + O c l 6 c d + d j 3 r r i Z D N H 8 A f O 5 w / E O I + + < / l a t e x i t > x (1) 2< l a t e x i t s h a 1 _ b a s e 6 4 = " 2 P q 9 E l 2 6 P g X 4V C 9 B e E 2 d f w R / n t Q = " > A A A B 8 H i c b V B N S w M x E J 3 1 s 9 a v q k c v w S L U S 9 k t R T 0 W v X i s Y D + k X U s 2 z b a h S X Z J s m J Z + i u 8 e F D E q z / H m / / G t N 2 D t j 4 Y e L w 3 w 8 y 8 I O Z M G 9 f 9 d l Z W 1 9 Y 3 N n N b + e 2 d 3 b 3 9 w s F h U 0 e J I r R B I h 6 p d o A 1 5 U z S h m G G 0 3 a s K B Y B p 6 1 g d D 3 1 W 4 9 U a R b J O z O O q S / w Q L K Q E W y s d P / U q z y k p c r Z p F c o u m V 3 B r R M v I w U I U O 9 V / j q 9 i O S C C o N 4 V j r j u f G x k + x M o x w O s l 3 E 0 1 j T E Z 4 Q D u W S i y o 9 t P Z w R N 0 a p U + C i N l S x o 0 U 3 9 P p F h o P R a B 7 R T Y D P W i N x X / 8 z q J C S / 9 l M k 4 M V S S + a I w 4 c h E a P o 9 6 j N F i e F j S z B R z N 6 K y B A r T I z N K G 9 D 8 B Z f X i b N S t k 7 L 1 d v q 8 X a V R Z H D o 7 h B E r g w Q X U 4 A b q 0 A A C A p 7 h F d 4 c 5 b w 4 7 8 7 H v H X F y W a O 4 A + c z x / F v o + / < / l a t e x i t > x (2) 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " X 6 / l 1 v z t v Q 4 N c q E c j O c c P 1 O o t f g = " > A A A B 8 H i c b V B N T w I x E J 3 F L 8 Q v 1 K O X R m K C F 7 K L R D 0 S v X j E R D 4 M r K R b C j S 0 3 U 3 b N Z I N v 8 K L B 4 3 x 6 s / x 5 r + x w B 4 U f M k k L + / N Z G Z e E H G m j e t + O 5 m V 1 b X 1 j e x m b m t 7 Z 3 c v v 3 / Q 0 G G s C K 2 T k I e q F W B N O Z O 0 b p j h t B U p i k X A a T M Y X U / 9 5 i N V m o X y z o w j 6 g s 8 k K z P C D Z W u n / q l h + S 4 t n p p J s v u C V 3 B r R M v J Q U I E W t m / / q 9 E I S C y o N 4 V j r t u d G x k + w M o x w O s l 1 Y k 0 j T E Z 4 Q N u W S i y o 9 p P Z w R N 0 Y p U e 6 o f K l j R o p v 6 e S L D Q e i w C 2 y m w G e p F b y r + 5 7 V j 0 7 / 0 E y a j 2 F B J 5 o v 6 M U c m R N P v U Y 8 p S g w f W 4 K J Y v Z W R I Z Y Y W J s R j k b g r f 4 8 j J p l E v e e a l y W y l U r 9 I 4 s n A E x 1 A E D y 6 g C j d Q g z o Q E P A M r / D m K O f F e X c + 5 q 0 Z J 5 0 5 h D 9 w P n 8 A x 0 S P w A = = < / l a t e x i t > x (3) 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " H k 1 3 l u 1 f 1 O E 1 o I 5 K f 8 F T u o + 7 g 8 Y = " > A A A B 8 H i c b V B N S w M x E J 3 1 s 9 a v q k c v w S L U S 9 k t R T 0 W v X i s Y D + k X U s 2 z b a h S X Z J s m J Z + i u 8 e F D E q z / H m / / G t N 2 D t j 4 Y e L w 3 w 8 y 8 I O Z M G 9 f 9 d l Z W 1 9 Y 3 N n N b + e 2 d 3 b 3 9 w s F h U 0 e J I r R B I h 6 p d o A 1 5 U z S h m G G 0 3 a s K B Y B p 6 1 g d D 3 1 W 4 9 U a R b J O z O O q S / w Q L K Q E W y s d P / U q z y k p e r Z p F c o u m V 3 B r R M v I w U I U O 9 V / j q 9 i O S C C o N 4 V j r j u f G x k + x M o x w O s l 3 E 0 1 j T E Z 4 Q D u W S i y o 9 t P Z w R N 0 a p U + C i N l S x o 0 U 3 9 P p F h o P R a B 7 R T Y D P W i N x X / 8 z q J C S / 9 l M k 4 M V S S + a I w 4 c h E a P o 9 6 j N F i e F j S z B R z N 6 K y B A r T I z N K G 9 D 8 B Z f X i b N S t k 7 L 1 d v q 8 X a V R Z H D o 7 h B E r g w Q X U 4 A b q 0 A A C A p 7 h F d 4 c 5 b w 4 7 8 7 H v H X F y W a O 4 A + c z x / I y o / B < / l a t e x i t > x (4) 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " y p 8 6 h 0 2 b W B u N d d o U 2 7 e R i 8 S / M R 4 = " > A A A B + 3 i c b V B N S 8 N A E N 3 U r 1 q / Y j 1 6 C R a h X k p S i n o s e v F Y w X 5 A G 8 N m u 2 m X b j Z h d y I t I X / F i w d F v P p H v P l v 3 L Y 5 a O u D g c d 7 M 8 z M 8 2 P O F N j 2 t 1 H Y 2 N z a 3 i n u l v b 2 D w 6 P z O N y R 0 W J J L R N I h 7 J n o 8 V 5 U z Q N j D g t B d L i k O f 0 6 4 / u Z 3 7 3 S c q F Y v E A 8 x i 6 o Z 4 J F j A C A Y t e W Z 5 6 t U f 0 w H Q K a Q x z q r O R e a Z F b t m L 2 C t E y c n F Z S j 5 Z l f g 2 F E k p A K I B w r 1 X f s G N w U S 2 C E 0 6 w 0 S B S N M Z n g E e 1 r K n B I l Z s u b s + s c 6 0 M r S C S u g R Y C / X 3 R I p D p W a h r z t D D G O 1 6 s 3 F / 7 x + A s G 1 m z I R J 0 A F W S 4 K E m 5 B Z M 2 D s I Z M U g J 8 p g k m k u l b L T L G E h P Q c Z V 0 C M 7 q y + u k U 6 8 5 l 7 X G f a P S v M n j K K J T d I a q y E F X q I n u U A u 1 E U F T 9 I x e 0 Z u R G S / G u / G x b C 0 Y + c w J + g P j 8 w e o J J Q z < / l a t e x i t > x pa(1) < l a t e x i t s h a 1 _ b a s e 6 4 = " e D y 2 x M C l E s C c 0 h c 2 M q w D B X 9 u g U w = " > A A A B + 3 i c b V B N S 8 N A E N 3 U r 1 q / Y j 1 6 C R a h X k p S i n o s e v F Y w X 5 A G 8 N m u 2 m X b j Z h d y I t I X / F i w d F v P p H v P l v 3 L Y 5 a O u D g c d 7 M 8 z M 8 2 P O F N j 2 t 1 H Y 2 N z a 3 i n u l v b 2 D w 6 P z O N y R 0 W J J L R N I h 7 J n o 8 V 5 U z Q N j D g t B d L i k O f 0 6 4 / u Z 3 7 3 S c q F Y v E A 8 x i 6 o Z 4 J F j A C A Y t e W Z 5 6 t U f 0 w H Q K a Q x z q r 1 i 8 w z K 3 b N X s B a J 0 5 O K i h H y z O / B s O I J C E V Q D h W q u / Y M b g p l s A I p 1 l p k C g a Y z L B I 9 r X V O C Q K j d d 3 J 5 Z 5 1 o Z W k E k d Q m w F u r v i R S H S s 1 C X 3 e G G M Z q 1 Z u L / 3 n 9 B I J r N 2 U i T o A K s l w U J N y C y J o H Y Q 2 Z p A T 4 T B N M J N O 3 W m S M J S a g 4 y r p E J z V l 9 d J p 1 5 z L m u N + 0 a l e Z P H U U S n 6 A x V k Y O u U B P d o R Z q I 4 K m 6 B m 9 o j c j M 1 6 M d + N j 2 V o w 8 p k T 9 A f G 5 w + p q p Q 0 < / l a t e x i t > x pa(2) < l a t e x i t s h a 1 _ b a s e 6 4 = " 5 / s C 9 6 o k T E / r I F k L c s m r U J H h d u g = " > A A A B + 3 i c b V D L S s N A F J 3 4 r P U V 6 9 L N Y B H q p i S 1 q M u i G 5 c V 7 A P a G C b T S T t 0 8 m D m R l p C f s W N C 0 X c + i P u / B u n b R b a e u D C 4 Z x 7 u f c e L x Z c g W V 9 G 2 v r G 5 t b 2 4 W d 4 u 7 e / s G h e V R q q y i R l L V o J C L Z 9 Y h i g o e s B R w E 6 8 a S k c A T r O O N b 2 d + 5 4 l J x a P w A a Y x c w I y D L n P K Q E t u W Z p 4 t Y e 0 z 6 w C a Q x y S o X 5 5 l r l q 2 q N Q d e J X Z O y i h H 0 z W / + o O I J g E L g Q q i V M + 2 Y n B S I o F T w b J i P 1 E s J n R M h q y n a U g C p p x 0 f n u G z 7 Q y w H 4 k d Y W A 5 + r v i Z Q E S k 0 D T 3 c G B E Z q 2 Z u J / 3 m 9 B P x r J + V h n A A L 6 W K R n w g M E Z 4 F g Q d c M g p i q g m h k u t b M R 0 R S S j o u I o 6 B H v 5 5 V X S r l X t y 2 r 9 v l 5 u 3 O R x F N A J O k U V Z K M r 1 E B 3 q I l a i K I J e k a v 6 M 3 I j B f j 3 f h Y t K 4 Z + c w x + g P j 8 w e r M J Q 1 < / l a t e x i t > x pa(3) < l a t e x i t s h a 1 _ b a s e 6 4 = " R P I m Q G 6 Z 2 X f s 2 Y A Y q t L x j U 0 T y U s = " > A A A B + 3 i c b V B N S 8 N A E N 3 U r 1 q / Y j 1 6 C R a h X k p S i n o s e v F Y w X 5 A G 8 N m u 2 m X b j Z h d y I t I X / F i w d F v P p H v P l v 3 L Y 5 a O u D g c d 7 M 8 z M 8 2 P O F N j 2 t 1 H Y 2 N z a 3 i n u l v b 2 D w 6 P z O N y R 0 W J J L R N I h 7 J n o 8 V 5 U z Q N j D g t B d L i k O f 0 6 4 / u Z 3 7 3 S c q F Y v E A 8 x i 6 o Z 4 J F j A C A Y t e W Z 5 6 t U f 0 w H Q K a Q x z q q N i 8 w z K 3 b N X s B a J 0 5 O K i h H y z O / B s O I J C E V Q D h W q u / Y M b g p l s A I p 1 l p k C g a Y z L B I 9 r X V O C Q K j d d 3 J 5 Z 5 1 o Z W k E k d Q m w F u r v i R S H S s 1 C X 3 e G G M Z q 1 Z u L / 3 n 9 B I J r N 2 U i T o A K s l w U J N y C y J o H Y Q 2 Z p A T 4 T B N M J N O 3 W m S M J S a g 4 y r p E J z V l 9 d J p 1 5 z L m u N + 0 a l e Z P H U U S n 6 A x V k Y O u U B P d o R Z q I 4 K m 6 B m 9 o j c j M 1 6 M d + N j 2 V o w 8 p k T 9 A f G 5 w + s t p Q 2 < / l a t e x i t > x pa(4) < l a t e x i t s h a 1 _ b a s e 6 4 = " 2 G 0 u 7 Z L B S R U N j L W y 5 y J i i / 2 8 k 4 A = " > A A A B + 3 i c b V D L S s N A F J 3 4 r P U V 6 9 L N Y B H q p i S l P p Z F N y 4 r 2 A e 0 M U y m k 3 b o 5 M H M j b S E / I o b F 4 q 4 9 U f c + T d O 2 y y 0 9 c C F w z n 3 c u 8 9 X i y 4 A s v 6 N t b W N z a 3 t g s 7 x d 2 9 / Y N D 8 6 j U V l E i K W v R S E S y 6 x H F B A 9 Z C z g I 1 o 0 l I 4 E n W M c b 3 8 7 8 z h O T i k f h A 0 x j 5 g R k G H K f U w J a c s 3 S x K 0 9 p n 1 g E 0 h j k l U u z j P X L F t V a w 6 8 S u y c l F G O p m t + 9 Q c R T Q I W A h V E q Z 5 t x e C k R A K n g m X F f q J Y T O i Y D F l P 0 5 A E T D n p / P Y M n 2 l l g P 1 I 6 g o B z 9 X f E y k J l J o G n u 4 M C I z U s j c T / / N 6 C f j X T s r D O A E W 0 s U i P x E Y I j w L A g + 4 Z B T E V B N C J d e 3 Y j o i k l D Q c R V 1 C P b y y 6 u k X a v a l 9 X 6 f b 3 c u M n j K K A T d I o q y E Z X q I H u U B O 1 E E U T 9 I x e 0 Z u R G S / G u / G x a F 0 z 8 p l j 9 A f G 5 w + u P J Q 3 < / l a t e x i t > x pa(5) < l a t e x i t s h a 1 _ b a s e 6 4 = " 5 q L n 6 S 2 k w 1 a D 1 7 / V t C 9 2 2 G S m I d k = " > A A A B + 3 i c b V B N S 8 N A E N 3 4 W e t X r E c v w S L U S 0 l K q R 6 L X j x W s B / Q x r D Z b t q l m 0 3 Y n U h L y F / x 4 k E R r / 4 R b / 4 b t 2 0 O 2 v p g 4 P H e D D P z / J g z B b b 9 b W x s b m 3 v 7 B b 2 i v s H h 0 f H 5 k m p o 6 J E E t o m E Y 9 k z 8 e K c i Z o G x h w 2 o s l x a H P a d e f 3 M 7 9 7 h O V i k X i A W Y x d U M 8 E i x g B I O W P L M 0 9 W q P 6 Q D o F N I Y Z 5 X G Z e a Z Z b t q L 2 C t E y c n Z Z S j 5 Z l f g 2 F E k p A K I B w r 1 X f s G N w U S 2 C E 0 6 w 4 S B S N M Z n g E e 1 r K n B I l Z s u b s + s C 6 0 M r S C S u g R Y C / X 3 R I p D p W a h r z t D D G O 1 6 s 3 F / 7 x + A s G 1 m z I R J 0 A F W S 4 K E m 5 B Z M 2 D s I Z M U g J 8 p g k m k u l b L T L G E h P Q c R V 1 C M 7 q y + u k U 6 s 6 j W r 9 v l 5 u 3 u R x F N A Z O k c V 5 K A r 1 E R 3 q I X a i K A p e k a v 6 M 3 I j B f j 3 f h Y t m 4 Y + c w p + g P j 8 w e v w p Q 4 < / l a t e x i t > x pa(6) < l a t e x i t s h a 1 _ b a s e 6 4 = " e 8 3 t 9 k d k t X a U f 6 w S Z + + E f V P n v e U = " > A A A B 8 H i c b V B N S w M x E J 3 1 s 9 a v q k c v w S L U S 9 m V o h 6 L X j x W 6 J e 0 a 8 m m 2 T Y 0 y S 5 J V i x L f 4 U X D 4 p 4 9 e d 4 8 9 + Y t n v Q 1 g c D j / d m m J k X x J x p 4 7 r f z s r q 2 v r G Z m 4 r v 7 2 z u 7 d f O D h s 6 i h R h D Z I x C P V D r C m n E n a M M x w 2 o 4 V x S L g t B W M b q Z + 6 5 E q z S J Z N + O Y + g I P J A s Z w c Z K 9 0 + 9 + k N a 8 s 4 m v U L R L b s z o G X i Z a Q I G W q 9 w l e 3 H 5 F E U G k I x 1 p 3 P D c 2 f o q V Y Y T T S b 6 b a B p j M s I D 2 r F U Y k G 1 n 8 4 O n q B T q / R R G C l b 0 q C Z + n s i x U L r s Q h s p 8 B m q B e 9 q f i f 1 0 l M e O W n T M a J o Z L M F 4 U J R y Z C 0 + 9 R n y l K D B 9 b g o l i 9 l Z E h l h h Y m x G e R u C t / j y M m m e l 7 2 L c u W u U q x e Z 3 H k 4 B h O o A Q e X E I V b q E G D S A g 4 B l e 4 c 1 R z o v z 7 n z M W 1 e c b O Y I / s D 5 / A H 4 j I / g < / l a t e x i t > x (1) T < l a t e x i t s h a 1 _ b a s e 6 4 = " T o V l X K o R K E s K 9 C W K L n l w 1 T 8 I D u s = " > A A A B 8 H i c b V B N T w I x E J 3 F L 8 Q v 1 K O X R m K C F 7 J L i H o k e v G I C V 8 G V t I t B R r a 7 q b t G s m G X + H F g 8 Z 4 9 e d 4 8 9 9 Y Y A 8 K v m S S l / d m M j M v i D j T x n W / n c z a + s b m V n Y 7 t 7 O 7 t 3 + Q P z x q 6 j B W h D Z I y E P V D r C m n E n a M M x w 2 o 4 U x S L g t B W M b 2 Z + 6 5 E q z U J Z N 5 O I + g I P J R s w g o 2 V 7 p 9 6 9 Y e k W D 6 f 9 v I F t + T O g V a J l 5 I C p K j 1 8 l / d f k h i Q a U h H G v d 8 d z I + A l W h h F O p 7 l u r G m E y R g P a c d S i Q X V f j I / e I r O r N J H g 1 D Z k g b N 1 d 8 T C R Z a T 0 R g O w U 2 I 7 3 s z c T / v E 5 s B l d + w m Q U G y r J Y t E g 5 s i E a P Y 9 6 j N F i e E T S z B R z N 6 K y A g r T I z N K G d D 8 J Z f X i X N c s m 7 K F X u K o X q d R p H F k 7 g F I r g w S V U 4 R Z q 0 A A C A p 7 h F d 4 c 5 b w 4 7 8 7 H o j X j p D P H 8 A f O 5 w / 6 E o / h < / l a t e x i t > x (2) T < l a t e x i t s h a 1 _ b a s e 6 4 = " 7 7 q m M v z s 9 h z p m H 1 W q 4 w Z P B k S I Z Q = " > A A A B 8 H i c b V D L S g N B E O y N r x h f U Y 9 e B o M Q L 2 F X g 3 o M e v E Y I S 9 J 1 j A 7 m U 2 G z M w u M 7 N i W P I V X j w o 4 t X P 8 e b f O H k c N L G g o a j q p r s r i D n T x n W / n c z K 6 t r 6 R n Y z t 7 W 9 s 7 u X 3 z 9 o 6 C h R h N Z J x C P V C r C m n E l a N 8 x w 2 o o V x S L g t B k M b y Z + 8 5 E q z S J Z M 6 O Y + g L 3 J Q s Z w c Z K 9 0 / d 2 k N a P D 8 d d / M F t + R O g Z a J N y c F m K P a z X 9 1 e h F J B J W G c K x 1 2 3 N j 4 6 d Y G U Y 4 H e c 6 i a Y x J k P c p 2 1 L J R Z U + + n 0 4 D E 6 s U o P h Z G y J Q 2 a q r 8 n U i y 0 H o n A d g p s B n r R m 4 j / e e 3 E h F d + y m S c G C r J b F G Y c G Q i N P k e 9 Z i i x P C R J Z g o Z m 9 F Z I A V J s Z m l L M h e I s v L 5 P G W c m 7 K J X v y o X K 9 T y O L B z B M R T B g 0 u o w C 1 U o Q 4 E B D z D K 7 w 5 y n l x 3 p 2 P W W v G m c 8 c w h 8 4 n z / 7 m I / i < / l a t e x i t > x (3) T < l a t e x i t s h a 1 _ b a s e 6 4 = " 8 O n 9 0 6 S M N d h W s v B D 3 W D a 6 2 C x T / g = " > A A A B 8 H i c b V B N S w M x E J 3 1 s 9 a v q k c v w S L U S 9 m V o h 6 L X j x W 6 J e 0 a 8 m m 2 T Y 0 y S 5 J V i x L f 4 U X D 4 p 4 9 e d 4 8 9 + Y t n v Q 1 g c D j / d m m J k X x J x p 4 7 r f z s r q 2 v r G Z m 4 r v 7 2 z u 7 d f O D h s 6 i h R h D Z I x C P V D r C m n E n a M M x w 2 o 4 V x S L g t B W M b q Z + 6 5 E q z S J Z N + O Y + g I P J A s Z w c Z K 9 0 + 9 + k N a q p x N e o W i W 3 Z n Q M v E y 0 g R M t R 6 h a 9 u P y K J o N I Q j r X u e G 5 s / B Q r w w i n k 3 w 3 0 T T G Z I Q H t G O p x I J q P 5 0 d P E G n V u m j M F K 2 p E E z 9 f d E i o X W Y x H Y T o H N U C 9 6 U / E / r 5 O Y 8 M p P m Y w T Q y W Z L w o T j k y E p t + j P l O U G D 6 2 B B P F 7 K 2 I D L H C x N i M 8 j Y E b / H l Z d I 8 L 3 s X 5 c p d p V i 9 z u L I w T G c Q A k 8 u I Q q 3 E I N G k B A w D O 8 w p u j n B f n 3 f m Y t 6 4 4 2 c w R / I H z + Q P 9 H o / j < / l a t e x i t > x (4) T < l a t e x i t s h a 1 _ b a s e 6 4 = " T N C X 4 W g o q L h 2 b N 3 s h G 3 + k m S S J x I = " > A A A C E X i c d V C 7 S g N B F J 3 1 b X x F L W 0 G g x C b M K t r N J 1 o Y 6 l i V M j G M D u 5 q 4 O z D 2 b u i m H Z X 7 D x V 2 w s F L G 1 s / N v n G g E F T 0 w c D j n X O 7 c E 6 R K G m T s z R k a H h k d G 5 + Y L E 1 N z 8 z O l e c X j k 2 S a Q F N k a h E n w b c g J I x N F G i g t N U A 4 8 C B S f B 5 W 7 f P 7 k C b W Q S H 2 E v h X b E z 2 M Z S s H R S p 1 y F c 5 y X 9 l 8 l 9 P D a u 4 H I b 0 u O u 5 Z T n 2 E a 8 x T X l Q 3 V o v V o l O u s B p r r D f W G W U 1 j 9 W 9 + p Y l j H m N N Y + 6 l v R R I Q P s d 8 q v f j c R W Q Q x C s W N a b k s x X b O N U q h o C j 5 m Y G U i 0 t + D i 1 L Y x 6 B a e c f F x V 0 x S p d G i b a v h j p h / p 9 I u e R M b 0 o s M m I 4 4 X 5 7 f X F v 7 x W h u F W O 5 d x m i H E 4 n N R m C m K C e 3 X Q 7 t S g 0 D V s 4 Q L L e 1 f q b j g m g u 0 J Z Z s C V + X 0 v / J 8 V r N r d e 8 A 6 + y v T O o Y 4 I s k W V S J S 7 Z J N t k j + y T J h H k h t y R B / L o 3 D r 3 z p P z / B k d c g Y z i + Q H n J d 3 q O W c 8 A = = < / l a t e x i t > e R(x pa(5) 1 )< l a t e x i t s h a 1 _ b a s e 6 4 = " r j y l c R m p x N / u 6 2 d u q 4 N r J W g a R X I= " > A A A C E H i c d V C 7 S g N B F J 3 1 b X x F L W 0 G g x i b M K t L N F 3 Q x l L F q J D E M D u 5 q 4 O z D 2 b u S s K y n 2 D j r 9 h Y K G J r a e f f O N E I K n p g 4 H D O u d y 5 x 0 + U N M j Y m z M y O j Y + M T k 1 X Z i Z n Z t f K C 4 u n Z g 4 1 Q I a I l a x P v O 5 A S U j a K B E B W e J B h 7 6 C k 7 9 q 7 2 B f 3 o N 2 s g 4 O s Z + A u 2 Q X 0 Q y k I K j l T r F d T j P W s r m u 5 w e l b O W H 9 B e 3 n G t i N D D L O F 5 u b q R b + S d Y o l V W G 2 r t s U o q 3 i s 6 l V 3 L G H M q 2 1 6 1 L V k g B I Z 4 q B T f G 1 1 Y 5 G G E K F Q 3 J i m y x J s Z 1 y j F A r y Q i s 1 k H B x x S + g a W n E Q z D t 7 O O g n K 5 Z p U u D W N s X I f 1 Q v 0 9 k P D S m H / o 2 G X K 8 N L + 9 g f i X 1 0 w x 2 G l n M k p S h E h 8 L g p S R T G m g 3 Z o V 2 o Q q P q W cK G l / S s V l 1 x z g b b D g i 3 h 6 1 L 6 P z n Z r L j V i n f o l e q 7 w z q m y A p Z J W X i k m 1 S J / v k g D S I I D f k j j y Q R + f W u X e e n O f P 6 I g z n F k m P + C 8 v A N K D J z H < / l a t e x i t > e R(x pa(6) 1 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " o u + P x I 7 Y p l i + z E + Y b Z G H B 7 L w b f A = " > A A A C E H i c d V C 7 S g N B F J 3 1 b X x F L W 0 G g x i b M I l L N F 3 Q x l L F q J D E M D u 5 q 0 N m H 8 z c l Y R l P 8 H G X 7 G x U M T W 0 s 6 / c a I R V P T A w O G c c 7 l z j x c r a Z C x N 2 d s f G J y a n p m N j c 3 v 7 C 4 l F 9 e O T V R o g U 0 R K Q i f e 5 x A 0 q G 0 E C J C s 5 j D T z w F J x 5 v f 2 h f 3 Y N 2 s g o P M F B D O 2 A X 4 b S l 4 K j l T r 5 T b h I W 8 r m u 5 w e F 9 O W 5 9 N + 1 q l Y E a G P a c y z Y n U r 2 8 o 6 + Q I r s d p 2 b Z t R V n J Z 1 a 3 u W s K Y W 6 u 4 t G z J E A U y w m E n / 9 r q R i I J I E S h u D H N M o u x n X K N U i j I c q 3 E Q M x F j 1 9 C 0 9 K Q B 2 D a 6 c d B G d 2 w S p f 6 k b Y v R P q h f p 9 I e W D M I P B s M u B 4 Z X 5 7 Q / E v r 5 m g v 9 t O Z R g n C K H 4 X O Q n i m J E h + 3 Q r t Q g U A 0 s 4 U J L + 1 c q r r j m A m 2 H O V v C 1 6 X 0 f 3 J a K Z W r J f f I L d T 3 R n X M k D W y T o q k T H Z I n R y Q Q 9 I g g t y Q O / J AO i u o x S w s h M U L R O J I Z p q T p b I = " > A A A C E H i c d V C 7 S g N B F J 3 1 b X x F L W 0 G g x i b M I l r N F 3 Q x j K K U S G J Y X Z y V w d n H 8 z c F c O y n 2 D j r 9 h Y K G J r a e f f O N E I K n p g 4 H D O u d y 5 x 4 u V N M j Y m z M y O j Y + M T k 1 n Z u Z n Z t f y C 8 u H Z s o 0 Q K a I l K R P v W 4 A S V D a K J E Ba e x B h 5 4 C k 6 8 y 7 2 B f 3 I F 2 s g o P M J + D J 2 A n 4 f S l 4 K j l b r 5 d T h L 2 8 r m e 5 w e F t O 2 5 9 P r r F u x I s I 1 p j HP i l s b 2 U b W z R d Y i d U 2 a 5 u M s p L L q m 5 1 x x L G 3 F r F p W V L B i i Q I R r d / G u 7 F 4 k k g B C F 4 s a 0 y i z G T s o 1 S q E g y 7 U T A z E X l / w c W p a G P A D T S T 8 O y u i a V X r U j 7 R 9 I d I P 9 f t E y g N j + o F n k w H H C / P b G 4 h / e a 0 E / Z 1 O K s M 4 Q Q j F 5 y I / U R Q j O m i H 9 q Q G g a p v C R d a 2 r 9 S c c E 1 F 2 g 7 z N k S v i 6 l / 5 P j S q l c L b k H b q G + O 6 x j i q y Q V V I k Z b J N 6 m S f N E i T C H J D 7 s g D e XR u n X v n y X n + j I 4 4 w 5 l l 8 g P O y z t K G Z z H < / l a t e x i t > e R(x pa(5) 2 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " 3 2 0V P k l R g E W h B 8 h n n E i R h 3 x n 5 c E = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 m k q M e i F 4 8 V 7 Q e 0 o W y 2 k 3 b p Z h N 2 N 0 I J / Q l e P C j i 1 V / k z X / j t s 1 B W x 8 M P N 6 b Y W Z e k A i u j e t + O 4 W 1 9 Y 3 N r e J 2 a W d 3 b / + g f H j U 0 n G q G D Z Z L G L V C a h G w S U 2 D T c C O 4 l C G g U C 2 8 H 4 d u a 3 n 1 B p H s t H M 0 n Q j + h Q 8 p A z a q z 0 Q P t e v 1 x x q + 4 c Z J V 4 O a l A j k a / / N U b x C y N U B o m q N Z d z 0 2 M n 1 F l O B M 4 L f V S j Q l l Y z r E r q W S R q j 9 b H 7 q l J x Z Z U D C W N m S h s z V 3 x M Z j b S e R I H t j K g Z 6 W V v J v 7 n d V M T X v s Z l 0 l q U L L F o j A V x M R k 9 j c Z c I X M i I k l l C l u b y V s R B V l x q Z T s i F 4 y y + v k t Z F 1 b u s 1 u 5 r l f p N H k c R T u A U z s G D K 6 j D H T S g C Q y G 8 A y v 8 O Y I 5 8 V 5 d z 4 W r Q U n n z m G P 3 A + f w D r h Y 2 S < / l a t e x i t > a 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " 9 p B g E q o x E O 5 l a 7 U v x 6 V S i K K c D 9 w = " > A A A B / X i c b V D J T s M w F H T K V s o W l h s X i w q p v U Q J R K W 9 V X D h W B B d p D Z E j u O 2 V p 1 F t o M o U c W v c O E A Q l z 5 D 2 7 8 D W 6 b A x R G s j S a e a P 3 P F 7 M q J C m + a X l l p Z X V t f y 6 4 W N z a 3 t H X 1 3 r y W i h G P S x B G L e M d D g j A a k q a k k p F O z A k K P E b a 3 u h i 6 r f v C B c 0 C m / k O C Z O g A Y h 7 V O M p J J c / Y D c p q U e U w E f w e v S v W u V y x N X L 5 q G W a v Y V R u a h m 1 a 9 m l N E X M G a G W k C D I 0 X P 2 z 5 0 c 4 C U g o M U N C d C 0 z l k 6 K u K S Y k U m h l w g S I z x C A 9 J V N E Q B E U 4 6 u 3 4 C j 5 X i w 3 7 E 1 Q s l n K k / E y k K h B g H n p o M k B y K R W 8 q / u d 1 E 9 m v O i k N 4 0 S S E M 8 X 9 R M G Z Q S n V U C f c o I l G y u C M K f q V o i H i C M s V W E F V Y K 1 + O W / p H V i W B X D v r K L 9 f O s j j w 4 B E e g B C x w B u r g E j R A E 2 D w A J 7 A C 3 j V H r V n 7 U 1 7 n 4 / m t C y z D 3 5 B + / g G 8 d 2 U R A = = < / l a t e x i t > e ( R(x1)) < l a t e x i t s h a 1 _ b a s e 6 4 = " J W A r M a w U J O h s / x Z I 8 V L N x s 1 A 7 o I = " > A A A B / X i c b V D L T s J A F J 3 i C / F V H z s 3 E 4 k J b J o W G 4 Q d 0 Y 1 L N A I m U J v p d I A J 0 0 d m p k Z s i L / i x o X G u P U / 3 P k 3 D t C F o i e Z 5 O S c e 3 L v H C 9 m V E j T / N J y S 8 s r q 2 v 5 9 c L G 5 t b 2 j r 6 7 1 x Z R w j F p 4 Y h F / M Z D g j A a k p a k k p G b m B M U e I x 0 v N H 5 1 O / c E S 5 o F F 7 L c U y c A A 1 C 2 q c Y S S W 5 + g G 5 T U s 9 p g I + g l e l e 7 d S L k 9 c v W g a Z r 1 q 1 2 x o G r Z p 2 S d 1 R c w Z o J W R I s j Q d P X P n h / h J C C h x A w J 0 b X M W D o p 4 p J i R i a F X i J I j P A I D U h X 0 R A F R D j p 7 P o J P F a K D / s R V y + U c K b + T K Q o E G I c e G o y Q H I o F r 2 p + J / X T W S / 5 q Q 0 j B N J Q j x f 1 E 8 Y l B G c V g F 9 y g m W b K w I w p y q W y E e I o 6 w V I U V V A n W 4 p f / k n b F s K q G f W k X G 2 d Z H X l w C I 5 A C V j g F D T A B W i C F s D g A T y B F / C q P W r P 2 p v 2 P h / N a V l m H / y C 9 v E N 8 2 S U R Q = = < / l a t e x i t > e ( R(x2)) < l a t e x i t s h a 1 _ b a s e 6 4 = " Y J K i g i s i K z Z N S D F 6 0 z j f Q s R d + w A = " > A A A B / X i c b V D L T s J A F J 3 i C / F V H z s 3 E 4 k J b J p W G o Q d 0 Y 1 L N A I m U J v p d I A J 0 0 d m p k Z s i L / i x o X G u P U / 3 P k 3 D t C F o i e Z 5 O S c e 3 L v H C 9 m V E j T / N J y S 8 s r q 2 v 5 9 c L G 5 t b 2 j r 6 7 1 x Z R w j F p 4 Y h F / M Z D g j A a k p a k k p G b m B M U e I x 0 v N H 5 1 O / c E S 5 o F F 7 L c U y c A A 1 C 2 q c Y S S W 5 + g G 5 T U s 9 p g I + g l e l e 7 d S L k 9 c v W g a Z r 1 q 1 2 x o G r Z p 2 Z W 6 I u Y M 0 M p I E W R o u v p n z 4 9 w E p B Q Y o a E 6 F p m L J 0 U c U k x I 5 N C L x E k R n i E B q S r a I g C I p x 0 d v 0 E H i v F h / 2 I q x d K O F N / J l I U C D E O P D U Z I D k U i 9 5 U / M / r J r J f c 1 I a x o k k I Z 4 v 6 i c M y g h O q 4 A + 5 Q R L N l Y E Y U 7 V r R A P E U d Y q s I K q g R r 8 c t / S f v E s K q G f W k X G 2 d Z H X l w C I 5 A C V j g F D T A B W i C F s D g A T y B F / C q P W r P 2 p v 2 P h / N a V l m H / y C 9 v E N 9 O u U R g = = < / l a t e x i t > e ( R(x3)) < l a t e x i t s h a 1 _ b a s e 6 4 = " z H M A D / E d N h y o 7 W v 2 3 O q 7 D X k E P 1 A = " > A A A B / X i c b V D J T s M w F H T K V s o W l h s X i w q p v U Q J R K W 9 V X D h W F A X p D Z E j u O 2 V p 1 F t o M o U c W v c O E A Q l z 5 D 2 7 8 D W 6 b A x R G s j S a e a P 3 P F 7 M q J C m + a X l l p Z X V t f y 6 4 W N z a 3 t H X 1 3 r y 2 i h G P S w h G L + I 2 H B G E 0 J C 1 J J S M 3 M S c o 8 B j p e K O L q d + 5 I 1 z Q K G z K c U y c A A 1 C 2 q c Y S S W 5 + g G 5 T U s 9 p g I + g t e l e 7 d Z L k 9 c v W g a Z q 1 i V 2 1 o G r Z p 2 a c 1 R c w Z o J W R I s j Q c P X P n h / h J C C h x A w J 0 b X M W D o p 4 p J i R i a F X i J I j P A I D U h X 0 R A F R D j p 7 P o J P F a K D / s R V y + U c K b + T K Q o E G I c e G o y Q H I o F r 2 p + J / X T W S / 6 q Q 0 j B N J Q j x f 1 E 8 Y l B G c V g F 9 y g m W b K w I w p y q W y E e I o 6 w V I U V V A n W 4 p f / k v a J Y V U M + 8 o u 1 s + z O v L g E B y B E r D A G a i D S 9 A A L Y D B A 3 g C L + B V e 9 S e t T f t f T 6 a 0 7 L M P v g F 7 e M b J 2 G U Z w = = < / l a t e x i t > e ( R(xT )) < l a t e x i t s h a 1 _ b a s e 6 4 = " D 6 v I S / 1 I G W 5 H V D r 1 j k n G a c W U W 6 Y = " > A A A B + H i c b V D L S g N B E O y N r x g f W f X o Z T A I E S T s h q A e g 1 4 8 R j A P S J Z l d j K b D J l 9 M D M r i W u + x I s H R b z 6 K d 7 8 G y f J H j S x o K G o 6 q a 7 y 4 s 5 k 8 q y v o 3 c 2 v r G 5 l Z + u 7 C z u 7 d f N A 8 O W z J K B K F N E v F I d D w s K W c h b S q m O O 3 E g u L A 4 7 T t j W 5 m f v u B C s m i 8 F 5 N Y u o E e B A y n x G s t O S a x U Z 5 7 F a f x q 5 9 j r B r n 7 l m y a p Y c 6 B V Y m e k B B k a r v n V 6 0 c k C W i o C M d S d m 0 r V k 6 K h W K E 0 2 m h l 0 g a Y z L C A 9 r V N M Q B l U 4 6 P 3 y K T r X S R 3 4 k d I U K z d X f E y k O p J w E n u 4 M s B r K Z W 8 m / u d 1 E + V f O S k L 4 0 T R k C w W + Q l H K k K z F F C f C U o U n 2 i C i W D 6 V k S G W G C i d F Y F H Y K 9 / P I q a V U r 9 k W l d l c r 1 a + z O P J w D C d Q B h s u o Q 6 3 0 I A m E E j g G V 7 h z X g 0 X o x 3 4 2 P R m j O y m S P 4 A + P z B 4 Q 3 k b U = < / l a t e x i t > P (x2|x1, a1) < l a t e x i t s h a 1 _ b a s e 6 4 = " n B e G O Y i S p F k h z Q f S q z X v 9 / i b / I Q = " > A A A B + H i c b V D L S g N B E O z 1 G e M j q x 6 9 D A Y h g o T d G N R j 0 I v H C O Y B y b L M T m a T I b M P Z m Y l c c 2 X e P G g i F c / x Z t / 4 y T Z g y Y W N B R V 3 X R 3 e T F n U l n W t 7 G y u r a + s Z n b y m / v 7 O 4 V z P 2 D p o w S Q W i D R D w S b Q 9 L y l l I G 4 o p T t u x o D j w O G 1 5 w 5 u p 3 3 q g Q r I o v F f j m D o B 7 o f M Z w Q r L b l m o V 4 a u e d P I 7 d y h r B b O X X N o l W 2 Z k D L x M 5 I E T L U X f O r 2 4 t I E t B Q E Y 6 l 7 N h W r J w U C 8 U I p 5 N 8 N 5 E 0 x m S I + 7 S j a Y g D K p 1 0 d v g E n W i l h / x I 6 A o V m q m / J 1 I c S D k O P N 0 Z Y D W Q i 9 5 U / M / r J M q / c l I W x o m i I Z k v 8 h O O V I S m K a A e E 5 Q o P t Y E E 8 H 0 r Y g M s M B E 6 a z y O g R 7 8 e V l 0 q y U 7 Y t y 9 a 5 a r F 1 n c e T g C I 6 h B D Z c Q g 1 u o Q 4 N I J D A M 7 z C m / F o v B j vx s e 8 d c X I Z g 7 h D 4 z P H 4 j U k b g = < / l a t e x i t > P (x3|x2, a2) < l a t e x i t s h a 1 _ b a s e 6 4 = " S Z R f U N 2 P q j e T i a zi M s G N 3 3 6 R u u A = " > A A A C A H i c b Z C 7 S g N B F I b P x l u M t 1 U L C 5 v B I E T Q s C t B L Y M 2 l h F y g 2 R Z Z i e T Z H D 2 w s y s J K z b + C o 2 F o r Y + h h 2 v o 2 T Z A t N / G H g 4 z / n c O b 8 X s S Z V J b 1 b e S W l l d W 1 / L r h Y 3 N r e 0 d c 3 e v K c N Y E N o g I Q 9 F 2 8 O S c h b Q h m K K 0 3 Y k K P Y 9 T l v e / c 2 k 3 n q g Q r I w q K t x R B 0 f D w L W Z w Q r b b n m Q a 0 0 c u u P I z e p n 9 n p K c I z O H H N o l W 2 p k K L Y G d Q h E w 1 1 / z q 9 k I S + z R Q h G M p O 7 Y V K S f B Q j H C a V r o x p J G m N z j A e 1 o D L B P p Z N M D 0 j R s X Z 6 q B 8 K / Q K F p u 7 v i Q T 7 U o 5 9 T 3 f 6 W A 3 l f G 1 i / l f r x K p / 5 S Q s i G J F A z J b 1 I 8 5 U i G a p I F 6 T F C i + F g D J o L p v y I y x A I T p T M r 6 B D s + Z M X o X l e t i / K l b t K s X q d x Z G H Q z i C E t h w C V W 4 h R o 0 g E A K z / A K b 8 a T 8 W K 8 G x + z 1 p y R z e z D H x m f P 4 0 i l R k = < / l a t e x i t > P (xT |xT 1, aT 1)< l a t e x i t s h a 1 _ b a s e 6 4 = " F 6 g 3 a J K e a S 3 r x q W i c J2 Z W A A i t Q 0 = " > A A A B 7 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B i y W R o h 6 L X j x W a G 2 h D W W z n b R L N 5 u w u x F K 6 I / w 4 k E R r / 4 e b / 4 b t 2 0 O 2 v p g 4 P H e D D P z g k R w b V z 3 2 y m s r W 9 s b h W 3 S z u 7 e / s H 5 c O j R x 2 n i m G L x S J W n Y B q F F x i y 3 A j s J M o p F E g s B 2 M 7 2 Z + + w m V 5 r F s m k m C f k S H k o e c U W O l N u 1 n z Q t v 2 i 9 X 3 K o 7 B 1 k l X k 4 q k K P R L 3 / 1 B j F L I 5 S G C a p 1 1 3 M T 4 2 d U G c 4 E T k u 9 V G N C 2 Z g O s W u p p B F q P 5 u f O y V n V h m Q M F a 2 p C F z 9 f d E R i O t J 1 F g O y N q R n r Z m 4 n / e d 3 U h D d + x m W S G p R s s S h M B T E x m f 1 O B l w h M 2 J i C W W K 2 1 s J G 1 F F m b E J l W w I 3 v L L q + T x s u p d V W s P t U r 9 N o + j C C d w C u f g w T X U 4 R 4 a 0 A I G Y 3 i G V 3 h z E u f F e X c+ F q 0 F J 5 8 5 h j 9 w P n 8 A w T W P M w = = < / l a t e x i t > aT 1 < l a t e x i t s h a 1 _ b a s e 6 4 = "Q R l F K T d Z F T H 2 T Z m C L u q 5 i s p B s x g = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 l E 1 G P R i 8 e K 9 g P a U D b b T b t 0 s w m 7 E 7 G E / g Q v H h T x 6 i / y 5 r 9 x 2 + a g r Q 8 G H u / N M D M v S K Q w 6 L r f T m F l d W 1 9 o 7 h Z 2 t r e 2 d 0 r 7 x 8 0 T Z x q x h s s l r F u B 9 R w K R R v o E D J 2 4 n m N A o k b w W j m 6 n f e u T a i F g 9 4 D j h f k Q H S o S C U b T S / V P P 6 5 U r b t W d g S w T L y c V y F H v l b + 6 / Z i l E V f I J D W m 4 7 k J + h n V K J j k k 1 I 3 N T y h b E Q H v G O p o h E 3 f j Y 7 d U J O r N I n Y a x t K S Q z 9 f d E R i N j x l F g O y O K Q 7 P o T c X / v E 6 K 4 Z W f C Z W k y B W b L w p T S T A m 0 7 9 J X 2 j O U I 4 t o U w L e y t h Q 6 o p Q 5 t O y Y b g L b 6 8 T J p n V e + i e n 5 3 X q l d 5 3 E U 4 Q i O 4 R Q 8 u I Q a 3 E I d G s B g A M / w C m + O d F 6 c d + d j 3 l p w 8 p l D + A P n 8 w c O n o 2 p < / l a t e x i t > x1 < l a t e x i t s h a 1 _ b a s e 6 4 = " A R 8 b w 1 i L V + h / T J 1 W t H I G v C Z C 5 c 0 = " > A A A B 6 n i c b V D L T g J B E O z F F + I L 9 e h l I j H x R H Y J U Y 9 E L x 4 x y i O B D Z k d e m H C 7 O x m Z t Z I C J / g x Y P G e P W L v P k 3 D r A H B S v p p F L V n e 6 u I B F c G 9 f 9 d n J r 6 x u b W / n t w s 7 u 3 v 5 B 8 f C o q e N U M W y w W M S q H V C N g k t s G G 4 E t h O F N A o E t o L R z c x v P a L S P J Y P Z p y g H 9 G B 5 C F n 1 F j p / q l X 6 R V L b t m d g 6 w S L y M l y F D v F b + 6 / Z i l E U r D B N W 6 4 7 m J 8 S d U G c 4 E T g v d V G N C 2 Y g O s G O p p B F q f z I / d U r O r N I n Y a x s S U P m 6 u + J C Y 2 0 H k e B 7 Y y o G e p l b y b + 5 3 V S E 1 7 5 E y 6 T 1 K B k i 0 V h K o i J y e x v 0 u c K m R F j S y h T 3 N 5 K 2 J A q y o x N p 2 B D 8 J Z f X i X N S t m 7 K F f v q q X a d R Z H H k 7 g F M 7 B g 0 u o w S 3 U o Q E M B v A M r / D m C O f F e X c+ F q 0 5 J 5 s 5 h j 9 w P n 8 A E C K N q g = = < / l a t e x i t > x2 < l a t e x i t s h a 1 _ b a s e 6 4 = " o H K E j B P a 1 N p T I 9 a c y Z H K j p o a 4 a I = " >A A A B 6 n i c b V D L T g J B E O z F F + I L 9 e h l I j H x R H a V q E e i F 4 8 Y 5 Z H A h s w O A 0 y Y n d 3 M 9 B r J h k / w 4 k F j v P p F 3 v w b B 9 i D g p V 0 U q n q T n d X E E t h 0 H W / n d z K 6 t r 6 R n 6 z s L W 9 s 7 t X 3 D 9 o m C j R j N d Z J C P d C q j h U i h e R 4 G S t 2 L N a R h I 3 g x G N 1 O / + c i 1 E Z F 6 w H H M / Z A O l O g L R t F K 9 0 / d 8 2 6 x 5 J b d G c g y 8 T J S g g y 1 b v G r 0 4 t Y E n K F T F J j 2 p 4 b o 5 9 S j Y J J P i l 0 E s N j y k Z 0 w N u W K h p y 4 6 e z U y f k x C o 9 0 o + 0 L Y V k p v 6 e S G l o z D g M b G d I c W g W v a n 4 n 9 d O s H / l p 0 L F C X L F 5 o v 6 i S Q Y k e n f p C c 0 Z y j H l l C m h b 2 V s C H V l K F N p 2 B D 8 B Z f X i a N s 7 J 3 U a 7 c V U r V 6 y y O P B z B M Z y C B 5 d Q h V u o Q R 0 Y D O A Z X u H N k c 6 L 8 + 5 8 z F t z T j Z z C H / g f P 4 A E a a N q w = = < / l a t e x i t > x3 < l a t e x i t s h a 1 _ b a s e 6 4 = " n F a E 6 W U N i v w f 3 M R M W O 7 i + m W Q o o M = " > A A A B 6 n i c b V D L S g N B E O y N r x h f U Y 9 e B o P g K e x K U I 9 B L x 4 j 5 g X J E m Y n v c m Q 2 d l l Z l Y M I Z / g x Y M i X v 0 i b / 6 N k 2 Q P m l j Q U F R 1 0 9 0 V J I J r 4 7 r f T m 5 t f W N z K 7 9 d 2 N n d 2 z 8 o H h 4 1 d Z w q h g 0 W i 1 i 1 A 6 p R c I k N w 4 3 A d q K Q R o H A V j C 6 n f m t R 1 S a x 7 J u x g n 6 E R 1 I H n J G j Z U e n n r 1 X r H k l t 0 5 y C r x M l K C D L V e 8 a v b j 1 k a o T R M U K 0 7 n p s Y f 0 K V 4 U z g t N B N N S a U j e g A O 5 Z K G q H 2 J / N T p + T M K n 0 S x s q W N G S u / p 6 Y 0 E j r c R T Y z o i a o V 7 2 Z u J / X i c 1 4 b U / 4 T J J D U q 2 W B S m g p i Y z P 4 m f a 6 Q G T G 2 h D L F 7 a 2 E D a m i z N h 0 C j Y E b / n l V d K 8 K H u X 5 c p 9 p V S 9 y e L I w w m c w j l 4 c A V V u I M a N I D B A J 7 h F d 4 c 4 b w 4 7 8 7 H o j X n Z D P H 8 A f O 5 w 9 D q o 3 M < / l a t e x i t > xT < l a t e x i t s h a 1 _ b a s e 6 4 = " 3 2 0 V P k l R g E W h B 8 h n n E i R h 3 x n 5 c E = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 m k q M e i F 4 8 V 7 Q e 0 o W y 2 k 3 b p Z h N 2 N 0 I J / Q l e P C j i 1 V / k z X / j t s 1 B W x 8 M P N 6 b Y W Z e k A i u j e t + O 4 W 1 9 Y 3 N r e J 2 a W d 3 b / + g f H j U 0 n G q G D Z Z L G L V C a h G w S U 2 D T c C O 4 l C G g U C 2 8 H 4 d u a 3 n 1 B p H s t H M 0 n Q j + h Q 8 p A z a q z 0 Q P t e v 1 x x q + 4 c Z J V 4 O a l A j k a / / N U b x C y N U B o m q N Z d z 0 2 M n 1 F l O B M 4 L f V S j Q l l Y z r E r q W S R q j 9 b H 7 q l J x Z Z U D C W N m S h s z V 3 x M Z j b S e R I H t j K g Z 6 W V v J v 7 n d V M T X v s Z l 0 l q U L L F o j A V x M R k 9 j c Z c I X M i I k l l C l u b y V s R B V l x q Z T s i F 4 y y + v k t Z F 1 b u s 1 u 5 r l f p N H k c R T u A U z s G D K 6 j D H T S g C Q y G 8 A y v 8 O Y I 5 8 V 5 d z 4 W r Q U n n z m G P 3 A + f w D r h Y 2 S < / l a t e x i t > a1 < l a t e x i t s h a 1 _ b a s e 6 4 = " W x k Z s 5 x R s 3 8 l J D 4 l 9 + F X g H m 0 H f I = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 l K U Y 9 F L x 4 r 2 l p o Q 9 l s J + 3 S z S b s b o Q S + h O 8 e F D E q 7 / I m / / G b Z u D t j 4 Y e L w 3 w 8 y 8 I B F c G 9 f 9 d g p r 6 x u b W 8 X t 0 s 7 u 3 v 5 B + f C o r e N U M W y x W M S q E 1 C N g k t s G W 4 E d h K F N A o E P g b j m 5 n / + I R K 8 1 g + m E m C f k S H k o e c U W O l e 9 q v 9 c s V t + r O Q V a J l 5 M K 5 G j 2 y 1 + 9 Q c z S C K V h g m r d 9 d z E + B l V h j O B 0 1 I v 1 Z h Q N q Z D 7 F o q a Y T a z + a n T s m Z V Q Y k j J U t a c h c / T 2 R 0 U j r S R T Y z o i a k V 7 2 Z u J / X j c 1 4 Z W f c Z m k B i V b L A p T Q U x M Z n + T A V f I j J h Y Q p n i 9 l b C R l R R Z m w 6 J R u C t / z y K m n X q t 5 F t X 5 X r z S u 8 z i K c A K n c A 4 e X E I D b q E J L W A w h G d 4 h T d H O C / O u / O x a C 0 4 + c w x / I H z + Q P t C Y 2 T < / l a t e x i t > a2 < l a t e x i t s h a 1 _ b a s e 6 4 = " b I I o z / l y Z L 8 Q q V T Z L C W z 5 B 2 G T 6 k = " > A A A B 7 X i c d V D L T g I x F O 3 g C / G F u n T T S E x w M 5 l B E N g R 3 b j E R B 4 J T E i n d K D S a S d t x 0 g I / + D G h c a 4 9 X / c + T d 2 Y E z U 6 E l u c n L O v b n 3 H j 9 i V G n H + b A y K 6 t r 6 x v Z z d z W 9 s 7 u X n 7 / o K 1 E L D F p Y c G E 7 P p I E U Y 5 a W m q G e l G k q D Q Z 6 T j T y 4 T v 3 N H p K K C 3 + h p R L w Q j T g N K E b a S O 1 m 8 X 7 g n g 7 y B c e u 1 5 x a t Q I d 2 1 k g I a V y 5 a w O 3 V Q p g B T N Q f 6 9 P x Q 4 D g n X m C G l e q 4 T a W + G p K a Y k X m u H y s S I T x B I 9 I z l K O Q K G + 2 u H Y O T 4 w y h I G Q p r i G C / X 7 x A y F S k 1 D 3 3 S G S I / V b y 8 R / / J 6 s Q 5 q 3 o z y K N a E 4 + W i I G Z Q C 5 i 8 D o d U E q z Z 1 B C E J T W 3 Q j x G E m F t A s q Z E L 4 + h f + T d s l 2 z + 3 y d b n Q u E j j y I I j c A y K w A V V 0 A B X o A l a A I N b 8 A C e w L M l r E f r x X p d t m a s d O Y Q / I D 1 9 g n L 6 o 6 k < / l a t e x i t > P (x1) < l a t e x i t s h a 1 _ b a s e 6 4 = " F 6 g 3 a J K e a S 3 r x q W i c J 2 Z W A A i t Q 0 = " > A A A B 7 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B i y W R o h 6 L X j x W a G 2 h D W W z n b R L N 5 u w u x F K 6 I / w 4 k E R r / 4 e b / 4 b t 2 0 O 2 v p g 4 P H e D D P z g k R w b V z 3 2 y m s r W 9 s b h W 3 S z u 7 e / s H 5 c O j R x 2 n i m G L x S J W n Y B q F F x i y 3 A j s J M o p F E g s B 2 M 7 2 Z + + w m V 5 r F s m k m C f k S H k o e c U W O l N u 1 n z Q t v 2 i 9 X 3 K o 7 B 1 k l X k 4 q k K P R L 3 / 1 B j F L I 5 S G C a p 1 1 3 M T 4 2 d U G c 4 E T k u 9 V G N C 2 Z g O s W u p p B F q P 5 u f O y V n V h m Q M F a 2 p C F z 9 f d E R i O t J 1 F g O y N q R n r Z m 4 n / e d 3 U h D d + x m W S G p R s s S h M B T E x m f 1 O B l w h M 2 J i C W W K 2 1 s J G 1 F F m b E J l W w I 3 v L L q + T x s u p d V W s P t U r 9 N o + j C C d w C u f g w T X U 4 R 4 a 0 A I G Y 3 i G V 3 h z E u f F e X c+ F q 0 F J 5 8 5 h j 9 w P n 8 A w T W P M w = = < / l a t e x i t > aT 1 transition probabilities P (x t+1 |a t , x t ) (i.e., the dynamics of the process), R t (x t , a t , x t+1 ) the reward for transitioning from x t to x t+1 under action a t at time step t, and T is the horizon. For simplicity of exposition we will consider discrete states and actions, but analogous results apply in the continuous case. Solving an MDP corresponds to finding a policy π t (a t |x t ) that maximizes the expectation of (a function of) the sum of the reward at each time step. The optimal policy can be different at each time step, i.e., non-stationary. We do not use a discount factor, but it can be trivially included in the reward function, since it is also non-stationary. Policies, states and actions at all time steps will be notedπ ≡ {π t (a t |x t )} T -1 t=1 , x ≡ {x t } T t=1 and a ≡ {a t } T -1 t=1 .In a state-factored MDP (factored MDP for short), each state x t factorizes into N e r.v. or entities {x(i) t } Ne i=1, each with cardinality N s , so it has an exponentially large state space of size N Ne s . Transitions factorize asP (x t+1 |a t , x t ) = Ne i=1 P (x (i) t+1 |x pa(i) t , a t ), where x pa(i) t is the subset of x t on which x (i)t+1 depends, which we will assume to be small to allow for a tabular definition of the transition without exponential cost (pa(i) stands in for "parents of i" ). For simplicity of notation, we will assume that the reward of factored MDPs at each time step depends only on the current state, and for tractability, that it can be decomposed in multiple additive subterms Rt (x t ) = Ne+Nr i=Ne+1 R t (x pa(i) t ),where x pa(i) t is a small subset of x t on which the (i -N e )-th reward depends, for a total of N r reward subterms. As before, this allows for a compact tabular representation of the reward. Including additional dependencies in the reward (on actions, or on the next state of an entity) is straightforward.For a more comprehensive introduction to MDPs, refer to (Puterman, 2014; Sutton, 2018) .Let's consider running different types of inference in the unnormalized1 factor graph shown in Fig. 1 [Left]. Marginal inference would compute the sum over all the x, a configurations (the partition function); MAP inference would compute the maximizing configuration (the posterior mode); and marginal MAP (MMAP) inference (see Liu and Ihler, 2013) would find the assignment of a that maximizes the summation over x conditional on that a. Although marginal, MAP, and MMAP inference are distinct, a lot is shared. They all target a "quantity of interest" (e.g., partition function, maximum probability state, best conditional partition function); they all produce a distribution as a result of inference (respectively, full posterior, delta at the mode, best conditional posterior); naïve computation requires a number of summations and/or maximizations exponential in the number of variables; and finally, they can all be represented as a variational inference (VI) problem. 2 The VI representation naturally leads to efficient message-passing solutions and approximate inference algorithms, as we show below.For the factor graph f (x, a) from Fig. 1 [Left], the VI problem 3 is max q(x,a) ⟨log f (x, a)⟩ q(x,a) + H type q (x, a) where q(x, a) is an arbitrary variational distribution over the variables of the factor Table 1 : Different types of inference from a variational perspective, including a proper "planning" inference type. They all share the same energy term E λ (q) defined in Eq. ( 3), and differ only in the entropy term. The closed-form expressions provide the optimal value of the bound, but are generally intractable. The general tractability of the bound maximization for MDPs is marked in the Tr column.All bounds are monotonically related, and listed in descending order, except the last two, whose relative ordering only applies when dynamics are deterministic. See Section 4.1 for details.Type of   Closed form for quant. of interest   Entropy term H type (q) for variational bound Tr inference ,a) Hq(x1) ,a) Hq(x1) ,a) Hq(x1)F λ = maxq F λ (q) F λ (q) = 1 λ (-E λ (q) + H type (q)) Marginal 4 1 λ log x,a P (x|a)e λR(x+ T -1 t=1 Hq(xt+1, at|xt) ✓ Planning 1 λ maxπ log⟨e λR(x,a) ⟩ P (x|a)π(a|x) Hq(x1) + T -1 t=1 Hq(xt+1|at, xt) ✓ M. MAP 1 λ maxa log x P (x|a)e λR(x+ T -1 t=1 Hq(xt+1, at|xt) -Hq(at) ✗ MAP 1 λ maxx,a log P (x|a)e λR(x,a) 0 ✓ Marginal U 1 λ log x,a P (x|a) 1 N T -1 a e λR(x+ T -1 t=1 (Hq(xt+1, at|xt) -log Na) ✓graph, the term -⟨log f (x, a)⟩ q(x,a) is known as the energy term, and H type q (x, a) is a particular entropy choice that will determine the inference type. It is a standard result, (e.g., Jordan et al., 1999) that using the Shannon entropy H q (x, a) results in marginal inference. Setting it to zero (aka the zero-temperature limit) corresponds to MAP inference (Weiss et al., 2012; Sontag et al., 2011; Wainwright et al., 2005; Kolmogorov, 2005; Martins et al., 2015) . Setting it to the conditional entropy H q (x|a) = H q (x, a) -H q (a) results in MMAP inference (Liu and Ihler, 2013) . Note that the only difference across VI problems is the weighting of the entropy terms.Despite the similarities, the computational complexity of these types of inference can differ significantly, even for tree-structured graphs. In particular, the entropy term for MMAP is not concave, and inference is NP-hard (Liu and Ihler, 2013) , whereas for marginal and MAP inference the entropy term is concave (the energy term is always linear), and inference is polynomial. 
methods: 
 In this section we introduce our VI framework, which we will use to derive a novel linear programming formulation of planning problems, a novel value belief propagation (VBP) algorithm and a novel closed form (sampling-free) approach to determinization.The main quantity of interest in this paper is the best exponential utility, which we will refer to simply as the utility. Given an MDP with horizon T and a risk parameter λ > 0, the utility is defined asF planning λ = 1 λ log max π x,a exp λ T -1 t=1 R t (x t , a t , x t+1 ) P (x 1 ) T -1 t=1 P (x t+1 |a t , x t )π t (a t |x t ) (1) = 1 λ max π log⟨exp(λR(x, a))⟩ P (x|a)π(a|x) ,where P (x|a) ≡ P (x 1 )T -1t=1 P (x t+1 |a t , x t ), R(x, a) ≡ T -1 t=1 R t (x t , a t , x t+1 ), and π(a|x) ≡ T -1 t=1 π t (a t |x t ).Observe that we can always set λ → 0 + to recover the standard planning setting in which we seek the best expected additive reward, so here we are tackling a strictly more general case. To be precise, if we take the limit F planning λ→0 + ≡ lim λ→0 + F planning λ = max π ⟨R(x, a)⟩ P (x|a)π(a|x) (Marthe et al., 2023) .The motivation for the introduction of λ is two-fold. On the one hand, by using a more general formulation of the reward, we can trade off between risk-neutral (λ → 0 + ) and risk-seeking (λ > 0)policies, adding a tunable parameter that makes the model more flexible, see (Marthe et al., 2023; Föllmer and Schied, 2011; Shen et al., 2014) for more details. On the other hand, it allows us to express the expected reward as a proper factor graph: note that Eq. ( 1) can be expressed as a product of factors involving not only the dynamics terms, but also the reward terms, allowing us to write it as F planning λ = 1 λ log max π x,a f (x, a)π(a|x), where f (x, a) is the factor graph of Fig. 1 [Left]. This factorization would not have been possible if we had simply used an additive reward. But at the same time, notice that we are not losing generality, since the additive reward case can be recovered by setting λ → 0 + . Alternatively, we could have achieved a factorized model by introducing an additional latent "selector" variable connected to all the rewards, but this would complicate our upcoming formulation and analysis. Furthermore, this formulation allows us to encompass prior work on planning as inference that uses λ > 0, such as (Levine, 2018) .We can turn this new quantity of interest, the utility, into the solution of a VI problem on the factor graph of Fig. 1 [Left]. Crucially, the factor graph includes the known dynamics and rewards terms, but not any policy term, since the policy is the outcome of inference.Theorem 1 (Variational formulation of planning). Given known dynamics P (x t+1 |a t , x t ), an initial distribution P (x 1 ) and reward functions R t (x t , a t , x t+1 ), the best exponential utility F planning λ from Eq. (1) can be expressed as the result of a concave variational optimization problemEQUATIONwith energy E λ (q) and entropy H planning (q) termsEQUATIONEQUATIONwhere q ≡ q(x, a) is an arbitrary distribution over the space of states and actions.Proof is in Appendix A. This entropy thus corresponds to "planning inference". The optimal policy at each time step corresponds to the optimal variational distribution q(a t |x t ). Table 1 lists the types of inference problems and their associated entropies (see Appendix E for their derivation and corresponding references). As we will discuss in Section 4, they display a monotonic ordering (in almost all cases).The VI problem Eq. ( 2) reduces to the standard one when λ = 1, and extends VI in a meaningful way in the presence of rewards, regardless of the type of inference used: rewards interact in an additive way when λ → 0 + , rather than the default multiplicative (or more precisely, exponentiated summation) interaction of λ = 1. Furthermore, it turns out that it is possible to take the λ → 0 + limit exactly, to obtain the dual LP formulation of an MDP (Puterman, 2014) .Corollary 1.1 (Additive limit). In the limit λ → 0 + , the concave problem Eq. (2) becomes the following linear program (LP):F planning λ→0 + = max q F planning λ→0 + (q) = max {q(xt,at)} T -1 t=1 T -1 t=1 ⟨R t (x t , a t , x t+1 )⟩ P (xt+1|at,xt)q(xt,at) s.t. q(x 1 ) = P (x 1 ); at+1 q(x t+1 , a t+1 ) = xt,at P (x t+1 |a t , x t )q(x t , a t ) ∀ t ; q(x t ) = at q(x t , a t ) ∀ t ; q(x t , a t ) ≥ 0 ∀t,which corresponds to the maximum expected reward F planning λ→0 + = max π ⟨R(x, a)⟩ P (x|a)π(a|x) .See Appendix B for proof.Factored MDPs (e.g., Fig. 1 [Right]) are loopy factor graphs with an exponentially large state space, so the previous approaches cannot be applied directly. An effective approximate marginal inference approach for this type of problem is loopy belief propagation (LBP). Since planning is now seen as a type of inference, we can create an analogue to LBP which we call value belief propagation (VBP).Following LBP, we make two approximations to Eq. ( 2) to make it tractable.First, we replace the variational distribution q with pseudo-marginals q. Eqs. ( 3) and ( 4) never access the full joint q(x, a), but only the local marginals of each factor. Pseudo-marginals are the collection of such local distributions, consistent at each variable, but not necessarily marginals of any distribution. Just like q is defined in a convex region called the marginal polytope M, q is defined in an outer convex region called the local polytope L that contains M (Weller et al., 2014) .Second, we replace the entropy H planning (q) with its Bethe approximationH planning Bethe (q) = Ne i=1 H q (x (i) 1 ) + T -1 t=1 Ne i=1 H q (x (i) t+1 |x pa(i) t , a t ) - Ne+Nr i=1 I q (x pa(i) t)whereI q (x pa(i) t ) = k∈pa(i) H q (x (k) t ) -H q (x pa(i) t) is the mutual information of the parents of x(i)t+1 , see Appendix C for details. This approximation is tractable as long as the factors (transition and rewards) are tractable, typically by connecting to a small number of parent variables. Note that the policy (which would connect to all the state variables in a time slice and introduce exponential cost) is not a factor in the graph.The term I q (x pa(i) t) is key. It always non-negative but neither concave nor convex in general and can be interpreted as the mutual information correcting the discrepancy between (a) the entropy of a collection of variables considered independently (as the output of the previous time step) and (b) the entropy of the same collection when considered jointly (as parents for the current time step). It makes the optimization problem harder, but also more accurate.For non-factored MDPs, I q (x pa(i) t ) = 0 and q = q, so we recover Eq. (2). In general factored MDPs this is not true. We can still choose to ignore this correction to obtain a concave boundEQUATIONThen, the planning Bethe approximation of the variational bound and its concave upper bound areEQUATIONWe see thatF planning λ ≥ F planning λ and F planning λ ≥ F planning λ .The former is trivial given the negative term removed. The latter follows from (a) switching the optimization domain from M to L ⊇ M, which can only increase the value of the bound, and (b) Eq. ( 5) corresponds to Eq. ( 4), but with joint entropies over entities replaced with sums of the entropies, which is an upper bound. The fact that F planning λ (q) is concave and upper bounds the exact utility has two advantages: it can be computed without local minima problems, and it is an admissible heuristic of the original utility, meaning that it can be used as a heuristic for algorithms that emit a certificate of optimality or infeasibility. Lemma (Additive limit for factored MDPs). In the limit λ → 0 + , the concave problem Eq. (7) becomes the following VI LP:F planning λ→0 + = max q F planning λ→0 + (q) = max q T t=1 Ne+Nr i=Ne ⟨R t (x pa(i) t )⟩ q(x pa(i) t ) s.t. q(x (i) 1 ) = P (x (i) 1 ) ∀i; q ∈ L q(x (i) t+1 ) = x pa(i) t ,at P (x (i) t+1 |x pa(i) t , a t )q(x pa(i) t , a t ) ∀x (i) t+1 , t, 1 ≤ i ≤ N ewhich upper bounds the max. expected reward F planning λ→0 + ≥ F planning λ→0 + = max π ⟨R(x, a)⟩ P (x|a)π(a|x) . Alternatively, the same expression can be obtained from Corollary 1.1 by relaxing the marginal polytope into the local polytope. Since it is a relaxation, the upper bounding is trivial.To the best of our knowledge, this is a novel VI LP formulation and it can be used to tractably (over) estimate the optimal expected reward in factored MDPs. Similarities with (Koller and Parr, 1999; Guestrin et al., 2003) are only surface level, see Section 5. F planning λ (q) from Eq. ( 7) can be maximized with a conic solver (or an LP solver if λ → 0 + ). The non-concave F planning λ (q) from Eq. ( 6) is more challenging. Conveniently, F planning λ (q) looks just like the Bethe free energy that motivates LBP, but with a different weighting of the local entropy terms.Multiple works consider modifying the entropy weighting in LBP, usually with the aim of "concavifying" the overall entropy term and developing convergent alternatives to LBP. In particular, (Hazan and Shashua, 2010) provides fixed-point message updates for arbitrary entropy weights. For the specific weighting of H planning Bethe (q) the message updates approach a singularity, which we will avoid by using (1ϵ)H planning Bethe (q)) + ϵH marginal Bethe (q). The resulting message passing algorithm updates are well-defined for any ϵ > 0, interpolate between "planning inference" and marginal inference, and can get arbitrarily close to the former by making ϵ → 0 + . The use of ϵ is not just a mathematical trick, but can be practically used to continuously anneal from LBP into VBP, which can improve convergence. See (Liu and Ihler, 2013) for an analogous technique with the same purpose.VBP inherits many of the properties of LBP: the message updates are not guaranteed to converge, but if they do, they do so at a fixed point of Eq. ( 6). Convergence can be improved by the use of damping and annealing. The precise message updates for the general case are provided in Appendix D.Computation associated with VBP scales as expected, O(T( Ne i=1 N a N |pa(i)|+1 s + Nr i=Ne+1 N |pa(i)| s )),where N e , N r , N a , N s have been defined in Section 2.1. Note that the derivation is straightforward. Each VBP iteration involves computing message updates for each factor in the graph. The cost is dominated by the blue factors (N e of them per time step) and green factors (N r of them per time step) in Fig. 1 It is instructive to look at the VBP updates for a standard, non-factored MDP. In this case, it is possible to take the limit ϵ → 0 + and get well-defined updates. For λ = 1 and a single reward at T Backward updates:m b (x T ) = e R T (x T ) ; m b (x t ) = max at Q(x t , a t ); Forward updates: m f (x 1 ) = P (x 1 ); m f (x t+1 ) = xt,at p(x t+1 |x t , a t )δ at,argmax a ′ t Q(xt,a ′ t ) m f (x t ) Optimal dist.: q(x t+1 , x t , a t ) ∝ m b (x t+1 )p(x t+1 |x t , a t )δ at,argmax a ′ t Q(xt,a ′ t ) m f (x t )where Q(x t , a t ) = xt+1 m b (x t+1 )p(x t+1 |x t , a t ) and δ j,k is a standard Kronecker delta that equals 1 when j = k and 0 otherwise. Iterating these updates converges in a single backward and forward pass to the global optimum. The backward messages correspond to the value function (hence the name VBP), and the familiar intermediate quantity Q(x t , a t ) matches the Q-function. The forward messages correspond to occupancy probabilities under the optimal policy. Thus, in a non-factored MDP we recover the standard Bellman backups, implementing value iteration and providing the exact solution. The same happens, conceptually, in a factored MDP, but only approximately, with the forward messages helping to determine where the backward approximation should be more precise.The previous presentation implies that all VI tricks are now applicable to planning. As an example, we can show that determinization (Yoon et al., 2008) , a technique from the planning literature to extend deterministic planning algorithms to stochastic domains, and that is usually computed via sampling, can be obtained in closed form by leveraging the variational formulation.To be more precise, we can compute F det. planning λ=1 (for MDPs) and F det. planning λ=1 (for factored MDPs) exactly as a single concave optimization problem (avoiding sampling) when the inner deterministic planning problem is solved with a standard LP MAP relaxation (Sontag et al., 2011) . Additionally we can prove that for factored MDPs F planning λ=1 ≤ F det. planning λ=1 (i.e., the superiority of the bound introduced here wrt determinization in the case of factored MDPs). See Appendix G for further details.4 The different types of inference and their adequacy for planning 4.1 Ranking inference types for planning As we show in Section 5, the term "planning as inference" has been used in the literature to refer to different inference types, none of which corresponds, to the best of our knowledge, with the "planning inference" from this work, which is exact. Table 1 associates each type of inference to a corresponding lower bound on its quantity of interest. Turns out that by inspecting the entropy term (since the energy is the same for all of them), we can also relate those lower bounds to one another for a given variational distribution q, resulting inF MAP λ (q) F marginal U λ (q) ≤ F MMAP λ (q) ≤ F planning λ (q) ≤ F marginal λ (q).This in turn means that for the optimal variational distribution of each type of inference we haveEQUATION)See Appendix F for proof. VI aims to maximize a lower bound on the quantity of interest, with tighter bounds generally indicating better performance. Since MMAP is, among the lower bounds, the tightest, it follows that MMAP inference is expected to be no worse and potentially better than all other common types of inference. However, as noted in Section 2.2, MMAP inference is particularly hard, even in trees, meaning that in the case of a non-factorial MDP like the one in Fig. 1 [Left], the computation of F MMAP λ is intractable, even though all the other quantities, including the one of interest, F planning λ , are exactly computable. What we can tractably compute is the lower boundF MMAP λ (q) ≤ F MMAP λand try to maximize it wrt q, but without guarantees of finding the optimal value. Thus, among the common inference types, MMAP seems a better choice, but it is either intractable or, if using VI, can run into local minima problems. This seems more acceptable in the factored MDP case, but it is disappointing that the problem persists for standard, non-factored MDPs. 
the stochasticity of the dynamics is key: 
 The energy term Eq. (3), which is common to all inference methods, contains subterms ⟨log P (x t+1 |a t , x t )⟩ q(xt+1,xt,at) (and ⟨log P (x 1 )⟩ q(x1) for the first state). When dynamics are deterministic (which we assume to also imply that P (x 1 ) is deterministic, i.e., the first state is known), this forces the optimal variational conditional to be q(x t+1 |a t , x t ) = P (x t+1 |a t , x t ) (and q(x 1 ) = P (x 1 ) for the first state), since any other choice would make those subterms, and therefore the bound, -∞. This affects the relationships of the quantities of interest, which are now (proof in Appendix F):F marginal U λ ≤ F MAP λ = F MMAP λ = F planning λ ≤ F marginal λ ,and justifies the use of MAP and MMAP inference as planning when dynamics are deterministic. When using approximate inference, if dynamics are close to deterministic, it might make more sense to choose the type of inference based on the quality of the approximation, rather than its tightness. If dynamics are stochastic, the suboptimality of MMAP can be explained as a lack of reactivity to the environment. Indeed, if we reduce the planning problem to a non-reactive policy π(a t |x t ) = π(a t ) we recover MMAP inference as optimal. We test this experimentally in Section 6 and further expand on it in Appendix H.2. MAP has the same problem, but additionally lacks integration over observation sequences ("trajectories"). Even with deterministic dynamics, marginal inference might not produce good utility estimates, but its action posterior will be proportional to the reward of the action sequence, so if we additionally assume exp(λR(x)) ∈ {0, 1} (i.e., pure planning where we want to attain any of a subset of states), it will produce optimal planning choices. 
related work: 
 As stated, the meaning of "planning as inference" is uneven across the literature. (Toussaint and Storkey, 2006) introduce the policy in the MDP factor graph and maximize the likelihood wrt to its parameters using EM. This is an exact approach, although it is more appropriate to say that it is planning as learning rather than a type of inference, since the EM process updates the parameters of the factor graph and inference typically operates on a graph with fixed parameters. (Levine, 2018 ) is a well-known reference that uses MAP inference to plan. It only considers the multiplicative setting λ = 1. Acknowledging the limitations of MAP inference under stochastic dynamics, it suggests a structured variational distribution where q(x t+1 |x t , a t ) = P (x t+1 |x t , a t ). Using this choice in Eq. ( 2) results in entropy terms cancelling with energy ones, which results in a simpler problem. Still, the rigid variational distribution prevents the optimal solution to the original problem from being found in general. In contrast, our entropy term allows for an unrestricted variational distribution. (Cui et al., 2015) introduces ARollout, which can be seen as running a single-forward-pass LBP to approximate marginal inference for each possible initial action, and then choosing the highest scoring initial action 5 , and is applicable to factored MDPs. In the follow-up works (Cui and Khardon, 2016; Cui et al., 2019) the authors develop conformant SOGBOFA, which approximates marginal-MAP inference by using ARollout in an inner loop and gradient descent to optimize over the action prior in an outer loop. A number of refinements are added for superior performance. This is a strong baseline and was the runner-up in the international probabilistic planning competition (IPPC) 2018, which agrees with our analysis from Section 4. (Lee et al., 2014; Lee et al., 2016) provide initial results on the connection between conformant planning and MMAP inference. Most works, such as (Attias, 2003) choose MAP inference for planning.Two frameworks (Palmieri et al., 2022; Wu and Khardon, 2022) have been recently introduced to analyze planning from a message-passing perspective. The former analyzes six update rules and their qualitative effect on the plans; the latter focuses on disentangling the inference direction 6 (either forward -from causes to outcomes-or backward -from outcomes to causes-) from the approximation type. This work provides two novel message-passing algorithms for factored MDPs: MFVI (mean field VI) and CSVI (collapsed state VI), using the planning tasks from IPPC 2011 as benchmark. We will compare with their results in Section 6.Influence diagrams (Matheson, 2005; Shachter, 2007) are used to represent general decision problems, and various approximate inference approaches have been developed, e.g., (Lee et al., 2018; Lee 5 If the choice of initial action is included in the inference process (rather than in an outer loop), it becomes an MMAP problem. However, this is a "degenerate" MMAP problem with a single maximization variable. To show this degeneracy, consider a non-factored MDP. Exact ARollout is tractable in the non-factored case. In contrast, exact SOGBOFA is not tractable even in the non-factored case because it maximizes over all decision variables.6 Note that the term inference direction may be misleading: the authors establish a direct equivalence between forward and MMAP inference, and between backward and marginal inference, regardless of the direction in which messages are passed or any other considerations (R. Khardon, personal communication, Oct 2024). et al., 2020) . Closest to our work, (Cheng et al., 2013; Chen et al., 2015) tackle graph-based MDPs, similar to factored MDPs, but with a factorized action space: multiple actions are taken at each time step, each locally affecting a single entity. This locality results in additional efficiencies, so direct application to a state-only-factored MDPs would still result in exponential cost.LP formulations for the solution non-stationary, finite-horizon MDPs have received significant attention over the last decade (e.g., Kumar et al., 2015; Bhattacharya and Kharoufeh, 2017; Altman, 2021; Bhat et al., 2023) , but they lack a variational perspective and do not generalize easily to handle state-factored MDPs. The LPs in (Koller and Parr, 1999; Guestrin et al., 2003; Malek et al., 2014) on the other hand do handle factored MDPs and have a closer connection to our work. The problem setup is slightly different, infinite-horizon MDPs with a stationary policy in their case vs our finite horizon MDPs, which allows us to use local non-stationary policies. More importantly, their solution approximately decomposes the value function into a linear combination of user-provided basis functions. The quantity and quality of these will determine the quality of the approximation, introducing additional design decisions. In VI planning we use the structure of the graph to determine the approximation, which is multiplicative over the value of backward messages, rather than additive. 
empirical validation: 
 Synthetic MDPs We generate 5, 000 synthetic factored MDPs structured as in Fig. 1 [Right] with random dynamics, all-or-nothing reward at the last time step, and controlled normalized entropies, defined as H MDP = i,x t ,a t H(p(x (i)t+1 |xt,at)) NeNaN Ne s log Ns ∈ [0, 1]. See Appendix H.1 for more details.They are purposefully small so that we can compute F marginal U , F MAP , F MMAP , F planning exactly, even though they are intractable in general. We also compute F marginal (tractable), and F MMAP (tractable bound, generally intractable optimization), which correspond to ARollout (Cui et al., 2015) and optimal SOGBOFA-LC* (Cui et al., 2019) , respectively. Finally, we include VBP (tractable, imperfect optimization of F planning (q)) and the tractable VI LP F planning and F planning λ=1 also improve over exact MMAP but not as much as VBP. For low stochasticity, exact MAP and MMAP dominate VBP. The (intractably optimal) SOGBOFA-LC* remains close to the exact MMAP. These results agree well with the theory and observations laid out in Section 4. We see good correlation between the accuracy of the utility estimation and the quality of the planning choices ([Left] and [Right] panels). ARollout and exact marginal seem to be an exception to this; this is explained in Section 4.2: for pure planning problems, with low stochasticity both methods are a constant away from the right utility and make good choices.We craft a multi-entity MDP in which the agent controls the level of reactivity (see Section 4.2) needed to solve the environment, but is penalized for lower ones. VBP keeps the reactivity at a maximum, to achieve a reward of 1. SOGBOFA-LC* "aware" that it cannot plan reactively (despite replanning), takes step to reduce it, getting a reward of 0.33. See Appendix H.2.International probabilistic planning competition tasks (IPPC) We follow (Wu and Khardon, 2022) and compare on the same tasks and with the same methods. We use the 6 different domains from IPPC2011, each with 10 instances (factored MDPs) of increasing difficulty, with given dynamics and (stationary) rewards, 40-step episodes, and mildly stochastic dynamics. As baselines, we use MFVI-Bwd (Wu and Khardon, 2022) , CSVI-Bwd (Wu and Khardon, 2022) , ARollout ( F marginal U λ=0 , see Cui et al., 2015) , and SOGBOFA-LC ( F MMAP λ=0 , see Cui et al., 2019) . We provide details about these competing methods in Appendix H.3. From our proposed variational framework, we use7 VI LP ( F planning λ=0), and VBP8 . ( F planning λ≈0 ).Fig. 3 shows the average cumulative reward for all domains and methods. Four domains are highly deterministic (H MDP < 0.05), but planning inference manages to be competitive wrt the best baselines. The other two are Game of Life and SysAdmin, which have an average H MDP of 0.18 and 0.23 respectively. We notice a significant advantage of our proposals wrt the most sophisticated method, SOGBOFA-LC ( F MMAP λ=0 ). This is consistent with our expectation of MMAP degrading with increased stochasticity (see Section 4). Elevators is well known for its challenging rewards (Cui et al., 2015) and the only one for which ARollout performs noticeably worse. In this domain, VBP manages to match or exceed SOGBOFA-LC on most instances. Overall, we observe that VBP is more consistent across varying stochasticities, matching the performance of the best method for each dataset. None of these domains reach the larger stochasticity levels shown in Fig. 2 where VBP dominates. VI LP also performs generally well, although not as well as VBP due to the missing mutual information mentioned in Section 3.2. See Appendix H.3 for details. 
discussion: 
 The variational framework offers a powerful tool to analyze and understand how different existing types of inference approximate planning, the key role of stochasticity, what the ideal type of inference for planning is, and how to design new approximations. We hope that the introduced VI perspective will further the understanding of existing methods and lead to novel planning algorithms.In this proof we will use two identities, the first is the variational identity (Jordan et al., 1999) :log x,a f (x, a) = max q(x,a) ⟨log f (x, a)⟩ q(x,a) + H(q(x, a)) (9)and the second is maxπ a q(a) log π(a) = max π(a)-H(q(a)) -KL(q(a)||π(a)) = a q(a) log q(a),which follows because the term π(a) is an arbitrary distribution that can make the KL divergence exactly zero (by choosing π(a) = q(a)). With this we can proceed to the main proof:F planning λ = 1 λ max π log a,x exp λ T -1 t=1 R t (x t , a t , x t+1 ) P (x 1 ) T -1 t=1 P (x t+1 |a t , x t )π t (a t |x t )Eq. ( 9)= 1 λ max π,q log P (x 1 ) T -1 t=1 exp(λR t (x t , a t , x t+1 ))P (x t+1 |a t , x t )π t (a t |x t ) q(x,a)+ H(q(x, a))= 1 λ max π,q -E λ (q) + H(q(x, a)) + T -1 t=1 ⟨log π t (a t |x t )⟩ q(xt,at) = 1 λ max q -E λ (q) + H q (x 1 ) + T -1 t=1 H q (x t+1 , a t |x t ) + ⟨max πt ⟨log π t (a t |x t )⟩ q(at|xt) ⟩ q(xt)Eq. ( 10)= 1 λ max q -E λ (q) + H q (x 1 ) + T -1 t=1 H q (x t+1 , a t |x t ) + ⟨⟨log q(a t |x t )⟩ q(at|xt) ⟩ q(xt) = 1 λ max q -E λ (q) + H q (x 1 ) + T -1 t=1 H q (x t+1 , a t |x t ) -H q (a t |x t ) = 1 λ max q -E λ (q) + H planning (q) = max q F planning λ (q),where we additionally see that we have chosen π t (a t |x t ) = q(a t |x t ), therefore, the optimal policy will be π t (a t |x t ) = q * (a t |x t ) where q * is the value of q that maximizes F planning λ (q).B Proof that for λ → 0 + the variational bound turns into an LPLet us rewrite the concave optimization functional Eq. (2) (derived in Appendix A) by combining the energy and entropy terms into KL divergences:F planning λ (q) = 1 λ -E λ (q) + H planning (q) = 1 λ -KL(q(x 1 )||P (x 1 )) - T -1 t=1 ⟨KL(q(x t+1 |x t , a t )||P (x t+1 |x t , a t ))⟩ q(xt,at) + ⟨λR t (x t , a t , x t+1 )⟩ q(xt+1,xt,at) = T -1 t=1 ⟨R t (x t , a t , x t+1 )⟩ q(xt+1,xt,at) - KL(q(x 1 )||P (x 1 )) + T -1 t=1 ⟨KL(q(x t+1 |x t , a t )||P (x t+1 |x t , a t ))⟩ q(xt,at) λIt is clear that if any of the KL terms are larger than 0, then lim λ→0 + F planning λ (q) = -∞ (for bounded rewards), whereas if all KL terms are 0, the limit is finite. That means that to maximize the bound wrt q in the λ → 0 + limit, we will choose q(x 1 ) = P (x 1 ) and q(x t+1 |x t , a t ) = P (x t+1 |x t , a t ), which allows to remove the KL terms and results in the (constrained) LP optimization of Corollary 1.1 (which also explicitly includes the marginalization constraints q ∈ M).The standard Bethe entropy of a factored MDP (Yedidia et al., 2005) , such as the one in Fig. 4 , is:H marginal Bethe (q) = Ne i=1 H q (x (i) 1 ) + T -1 t=1 H Bethe (q xt,at ) - Ne i=1 H q (x (i) t ) + Ne i=1 H q (x (i) t+1 , x pa(i) t , a t ) -H q (x pa(i) t , a t ) ,where we use x pa(i) tto refer to the "parent" variables. To simplify notation, when i ∈ 1, . . . , N e , x pa(i) tis the collection variables on which the distribution of x(i)t+1 depends according to the dynamics model, but when i ∈ N e + 1, . . . , N e + N r , x pa(i) tis the collection of variables on which the (i -N e )-th reward depends. See also Fig. 4 for clarification on the notation of parents of dynamics and rewards. The Bethe entropy above was defined, for conciseness, in terms of the Bethe entropy of a subset of the variables in a single time slice (current state and action, but not next state):H Bethe (q xt,at ) =(1 -N e )H q (a t ) + Ne i=1 H q (x pa(i) t , a t ) + Ne+Nr i=Ne+1 H q (x pa(i) t ) - Ne+Nr i=1 k∈pa(i) H q (x (k) t ) + Ne i=1 H q (x (i) t ).Finally, the Bethe entropy of the states of factored MDP isH Bethe (q xt ) = Ne i=1 H q (x (i) t ) + Ne+Nr i=1 H q (x pa(i) t ) - k∈pa(i) H q (x (k) t ) = Ne i=1 H q (x (i) t ) - Ne+Nr i=1 I q (x pa(i) t ) where I q (x pa(i) t) is the mutual information among the parents of variable x (i) t+1 . Note that all the Bethe entropy definitions are linear combinations of standard Shannon entropies defined over subsets of variables in the factor graph. The subsets are defined by the factor graph, as groups of variables connected by the same factor. The idea of the Bethe entropy approximation is to sum the entropies of all such subsets and then discount the "overcounted" entropy corresponding to variables that appear in multiple subsets. The pseudo-marginals q ≡ {q(x(i) t+1 , x pa(i) t , a t )} t=T -1,i=Ne t=1,i=1 ∪ {q(x pa(r) t )} t=T,r=Ne+Nr t=1,r=Ne+1are all the local distributions that correspond to each factor. The pseudo-marginals are locally consistent at the variables, i.e., two pseudo-marginals that contain the same variable should provide the same marginal for that variable. However, there is no further need for consistency, and in particular, they do not need to correspond to the marginals of global joint distribution. The (convex) domain of pseudo-marginals contains the (also convex) domain of the marginals, but it is larger, so switching from marginals to pseudo-marginals in any optimization problem relaxes it and provides an upper bound on the original optimization problem. See (Weller et al., 2014) for more details. For convenience, we have also defined some subsets of the pseudo-marginals: qxt,at ≡ {q(xpa(i) t , a t )} i=Ne i=1 ∪ {q(x pa(r) t )} r=Ne+Nr r=Ne+1and qxt ≡ {q(xpa(i) t )} i=Ne+Nr i=1 .Since the planning entropy is a linear combination of the standard entropy of the factor graph H marginal (q) and two local entropies per time step, we can simply approximate each Shannon entropy by its corresponding Bethe entropy to get the Bethe planning entropyH planning (q) = H marginal (q) + T -1 t=1 H q (x t ) -H q (x t , a t ) ≈ H marginal Bethe (q) + T -1 t=1 H Bethe (q xt ) -H Bethe (q xt,at ) = Ne i=1 H q (x (i) 1 ) + T -1 t=1 Ne i=1 H q (x (i) t+1 |x pa(i) t , a t ) - Ne+Nr i=1 I q (x pa(i) t ) = H planning Bethe (q).Note that we sometimes use the superscript marginal for consistency with the main text, but the marginal entropy is simply the standard entropy so that superscript can be safely dropped.We are interested in optimizing the cost function1 λ max q -E λ (q) + ϵH marginal Bethe (q) + (1 -ϵ)H planning Bethe (q)As we saw in Appendix C, H marginal Bethe (q) and H planning Bethe (q) are linear combinations of local entropies over small subsets of variables defined by the factor graph, therefore so is their linear combination. This score function can be seen as a standard Bethe free energy with non-standard entropy weightings. We can directly derive LBP-like message updates by using these modified weights instead (Hazan and Shashua, 2010) , resulting in the following VBP message updatesQ(x pa(i) t , a t ) = x (i) t+1 m b (x (i) t+1 )p(x (i) t+1 |x pa(i) t , a t ) m b (x pa(i) t ) = a (Q(x pa(i) t , a t )n (i) (a t )) 1 ϵ ϵ m (i) (a t ) = x pa(i) t Q(x pa(i) t , a t ) m b (x pa(i) t ) 1 ϵ m f (x pa(i) t )m b (x pa(i) t ) ϵ n (i) (a t ) = k̸ =i m (k) (a t ) m f (x (i) t+1 ) = x pa(i) t ,a Q(x pa(i) t , a t )n (i) (a t ) m b (x pa(i) t ) 1 ϵ m f (x pa(i) t )m b (x pa(i) t ) p(x (i) t+1 |x pa(i) t , a t ) Q(x pa(i) t , a t ) m f (x pa(i) t ) = k∈pa(i) n (i) f (x (k) t ) n (i) f (x (j) t ) = m f (x (j) t ) k|j∈pa(k),k̸ =i n (k) b (x (j) t ) towards parents of entity i n (i) b (x (j) t ) = {x (k) t } k̸ =j m b (x pa(i) t ) k̸ =i n (i) f (x (k) t ) from parents of entity i m b (x (j) t ) = k|j∈pa(k) n (k) b (x (j) t )The following messages should be held constantm b (x pa(i) t ) = exp(λR(x pa(i) t )) ∀i > N e m f (x (i) 1 ) = P (x (i) 1 )See Fig. 4 to track the correspondence between the above messages and the factor graph of the factored MDP. Note that most updates correspond exactly with standard loopy BP, and only a few (the ones involving ϵ) are specific to VBP. These messages updates should be iterated until convergence or for a fixed number of iterations. Two tricks to improve convergence are (a) damping the message updates in log space; (b) as the iterations progress, anneal between LBP (ϵ = 1) and VBP (very small ϵ). We typically use both, with a damping of 0.5 (i.e., the mean of the old and the new message in log space) and anneal by using as ϵ(iter) = max{0.01, 1.0/iter}, where "iter" is the iteration number.Scheduling also plays a role in convergence. We propagate the messages by alternating backward and forward schedules in an outer loop, and solving each time slice to convergence in an inner loop.We did observe a correlation between the quality of the solutions and VBP converging.< l a t e x i t s h a 1 _ b a s e 6 4 = "s i L 0 n U R l n t H U h Z v / v U 8 w 6 g p W f B Y = " > A A A B 8 H i c b V B N S w M x E J 3 1 s 9 a v q k c v w S L U S 9 n V o h 6 L X j x W s B / S r i W b Z t v Q J L s k W b E s / R V e P C j i 1 Z / j z X 9 j 2 u 5 B W x 8 M P N 6 b Y W Z e E H O m j e t + O 0 v L K 6 t r 6 7 m N / O b W 9 s 5 u Y W + / o a N E E V o n E Y 9 U K 8 C a c i Z p 3 T D D a S t W F I u A 0 2 Y w v J 7 4 z U e q N I v k n R n F 1 B e 4 L 1 n I C D Z W u n / q n j 2 k J e 9 k 3 C 0 U 3 b I 7 B V o k X k a K k K H W L X x 1 e h F J B J W G c K x 1 2 3 N j 4 6 d Y G U Y 4 H e c 7 i a Y x J k P c p 2 1 L J R Z U + + n 0 4 D E 6 t k o P h Z G y J Q 2 a q r 8 n U i y 0 H o n A d g p s B n r e m 4 j / e e 3 E h J d + y m S c G C r J b F G Y c G Q i N P k e 9 Z i i x P C R J Z g o Z m 9 F Z I A V J s Z m l L c h e P M v L 5 L G a d k 7 L 1 d u K 8 X q V R Z H D g 7 h C E r g w Q V U 4 Q Z q U A c C A p 7 h F d 4 c 5 b w 4 7 8 7 H r H X J y W Y O 4 A + c z x / F w o + / < / l a t e x i t >x(1) 3< l a t e x i t s h a 1 _ b a s e 6 4 = " x O C P R a G 3 K Z U t I m + n h T y x p L m l f z E = " > A A A B 8 H i c b V B N T w I x E J 3 F L 8 Q v 1 K O X R m K C F 7 K L R D 0 S v X j E R D 4 M r K R b C j S 0 3 U 3 b N Z I N v 8 K L B 4 3 x 6 s / x 5 r + x w B 4 U f M k k L + / N Z G Z e E H G m j e t + O 5 m V 1 b X 1 j e x m b m t 7 Z 3 c v v 3 / Q 0 G G s C K 2 T k I e q F W B N O Z O 0 b p j h t B U p i k X A a T M Y X U / 9 5 i N V m o X y z o w j 6 g s 8 k K z P C D Z W u n / q n j 0 k x f L p p J s v u C V 3 B r R M v J Q U I E W t m / / q 9 E I S C y o N 4 V j r t u d G x k + w M o x w O s l 1 Y k 0 j T E Z 4 Q N u W S i y o 9 p P Z w R N 0 Y p U e 6 o f K l j R o p v 6 e S L D Q e i w C 2 y m w G e p F b y r + 5 7 V j 0 7 / 0 E y a j 2 F B J 5 o v 6 M U c m R N P v U Y 8 p S g w f W 4 K J Y v Z W R I Z Y Y W J s R j k b g r f 4 8 j J p l E v e e a l y W y l U r 9 I 4 s n A E x 1 A E D y 6 g C j d Q g z o Q E P A M r / D m K O f F e X c+ 5 q 0 Z J 5 0 5 h D 9 w P n 8 A x 0 i P w A = = < / l a t e x i t >x(2) 3< l a t e x i t s h a 1 _ b a s e 6 4 = "EQUATION< l a t e x i t s h a 1 _ b a s e 6 4 = " E 1 r i 4 K X B 8 p 6 k3 r L x M U h K T F S Y e v A = " > A A A B 8 3 i c d V D L T g J B E O z F F + I L 9 e h l I j G B y 2 Y X Q e B G 9 O I R E w E T W M n s M M C E 2 U d m Z o 1 k w 2 9 4 8 a A x X v 0 Z b / 6 N s 7 A m a r S S T i p V 3 e n u c k P O p L K s D y O z s r q 2 v p H d z G 1 t 7 + z u 5 f c P O j K I B K F t E v B A 3 L h Y U s 5 8 2 l Z M c X o T C o o 9 l 9 O u O 7 1 I / O 4 d F Z I F / r W a h d T x 8 N h n I 0 a w 0 l K / V b w f 2 L d x s V y a l w b 5 g m U 2 6 l a 9 V k W W a S 2 Q k H K l e t p A d q o U I E V r k H / v D w M S e d R X h G M p e 7 Y V K i f G Q j H C 6 T z X j y Q N M Z n i M e 1 p 6 m O P S i d e 3 D x H J 1 o Z o l E g d P k K L d T v E z H 2 p J x 5 r u 7 0 s J r I 3 1 4 i / u X 1 I j W q O z H z w 0 h R n y w X j S K O V I C S A N C Q C U o U n 2 m C i W D 6 V k Q m W G C i d E w 5 H c L X p + h / 0 i m b 9 p l Z u a o U m u d p H F k 4 g m M o g g 0 1 a M I l t K A N B E J 4 g C d 4 N i L j 0 X g x X p e t G S O d O Y Q f M N 4 + A Y Z c k L k = < / l a t e x i t > P (x (2) 1 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " 8 R c n + l i G g A d E f + a C n W m N B P M 2 2 h w = " > A A A B 8 H i c b V B N S w M x E J 2 t X 7 V + V T 1 6 C R a h X s q u F P V Y 9 O K x g v 2 Q d i 3 Z N N u G J t k l y Y p l 6 a / w 4 k E R r / 4 c b / 4 b 0 3 Y P 2 v p g 4 P H e D D P z g p g z b V z 3 2 8 m t r K 6 t b + Q 3 C 1 v b O 7 t 7 x f 2 D p o 4 S R W i D R D x S 7 Q B r y p m k D c M M p + 1 Y U S w C T l v B 6 H r q t x 6 p 0 i y S d 2 Y c U 1 / g g W Q h I 9 h Y 6 f 6 p 5 z 2 k Z e 9 0 0 i u W 3 I o 7 A 1 o m X k Z K k K H e K 3 5 1 + x F J B J W G c K x 1 x 3 N j 4 6 d Y G U Y 4 n R S 6 i a Y x J i M 8 o B 1 L J R Z U + + n s 4 A k 6 s U o f h Z G y J Q 2 a q b 8 n U i y 0 H o v A d g p s h n r R m 4 r / e Z 3 E h J d + y m S c G C r J f F G Y c G Q i N P 0 e 9 Z m i x P C x J Z g o Z m 9 F Z I g V J s Z m V L A h e I s v L 5 P m W c U 7 r 1 R v q 6 X a V R Z H H o 7 g G M r g w Q X U 4 A b q 0 A A C A p 7 h F d 4 c 5 b w 4 7 8 7 H v D X n Z D O H 8 A f O 5 w / C r o + 9 < / l a t e x i t >x(1) 1< l a t e x i t s h a 1 _ b a s e 6 4 = " e s 0 F a W k g S 5 w Q x r N a v q r i HN Z L Q q 4 = " > A A A B 8 H i c b V B N S w M x E J 3 1 s 9 a v q k c v w S L U S 9 k t R T 0 W v X i s Y D + k X U s 2 z b a h S X Z J s m J Z + i u 8 e F D E q z / H m / / G t N 2 D t j 4 Y e L w 3 w 8 y 8 I O Z M G 9 f 9 d l Z W 1 9 Y 3 N n N b + e 2 d 3 b 3 9 w s F h U 0 e J I r R B I h 6 p d o A 1 5 U z S h m G G 0 3 a s K B Y B p 6 1 g d D 3 1 W 4 9 U a R b J O z O O q S / w Q L K Q E W y s d P / U 8 x 7 S U u V s 0 i s U 3 b I 7 A 1 o m X k a K k K H e K 3 x 1 + x F J B J W G c K x 1 x 3 N j 4 6 d Y G U Y 4 n e S 7 i a Y x J i M 8 o B 1 L J R Z U + + n s 4 A k 6 t U o f h Z G y J Q 2 a q b 8 n U i y 0 H o v A d g p s h n r R m 4 r / e Z 3 E h J d + y m S c G C r J f F G Y c G Q i N P 0 e 9 Z m i x P C x J Z g o Z m 9 F Z I g V J s Z m l L c h e I s v L 5 N m p e y d l 6 u 3 1 W L t K o s j B 8 d w A i X w 4 A J q c A N 1 a A A B A c / w C m + O c l 6 c d + d j 3 r r i Z D N H 8 A f O 5 w / E N I + + < / l a t e x i t > x (2) 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " 0 f l w I Y z z a c t o B 6 K T o L f R q R c N a + 0 = " > A A A B + 3 i c b V B N S 8 N A E N 3 4 W e t X r E c v i 0 W o l 5 J I U Y 9 F L x 4 r 2 A 9 o Y 9 h s t + 3 S z S b s T q Q l 5 K 9 4 8 a C I V / + I N / + N 2 z Y H b X 0 w 8 H h v h p l 5 Q S y 4 B s f 5 t t b W N z a 3 t g s 7 x d 2 9 / Y N D + 6 j U 0 l G i K G v S S E S q E x D N B J e s C R w E 6 8 S K k T A Q r B 2 M b 2 d + + 4 k p z S P 5 A N O Y e S E Z S j 7 g l I C R f L s 0 8 d 3 H t A d s A m l M s o p 7 n v l 2 2 a k 6 c + B V 4 u a k j H I 0 f P u r 1 4 9 o E j I J V B C t u 6 4 T g 5 c S B Z w K l h V 7 i W Y x o W M y Z F 1 D J Q m Z 9 t L 5 7 R k + M 0 o f D y J l S g K e q 7 8 n U h J q P Q 0 D 0 x k S G O l l b y b + 5 3 U T G F x 7 K Z d x A k z S x a J B I j B E e B Y E 7 n P F K I i p I Y Q q b m 7 F d E Q U o W D i K p o Q 3 O W X V 0 n r o u p e V m v 3 t X L 9 J o + j g E 7 Q K a o g F 1 2 h O r p D D d R E F E 3 Q M 3 p F b 1 Z m v V j v 1 s e i d c 3 K Z 4 7 R H 1 i f P 6 a R l D I = < / l a t e x i t > x pa(1) 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " O 2 S T b u f U u W x b z J U w r l k 5 Z t W D h N 4 = " > A A A B + 3 i c b V B N S 8 N A E N 3 U r 1 q / Y j 1 6 C R a h X k p S i n o s e v F Y w X 5 A G 8 N m u 2 m X b j Z h d y I t I X / F i w d F v P p H v P l v 3 L Y 5 a O u D g c d 7 M 8 z M 8 2 P O F N j 2 t 1 H Y 2 N z a 3 i n u l v b 2 D w 6 P z O N y R 0 W J J L R N I h 7 J n o 8 V 5 U z Q N j D g t B d L i k O f 0 6 4 / u Z 3 7 3 S c q F Y v E A 8 x i 6 o Z 4 J F j A C A Y t e W Z 5 6 j m P 6 Q D o F N I Y Z 9 X 6 R e a Z F b t m L 2 C t E y c n F Z S j 5 Z l f g 2 F E k p A K I B w r 1 X f s G N w U S 2 C E 0 6 w 0 S B S N M Z n g E e 1 r K n B I l Z s u b s + s c 6 0 M r S C S u g R Y C / X 3 R I p D p W a h r z t D D G O 1 6 s 3 F / 7 x + A s G 1 m z I R J 0 A F W S 4 K E m 5 B Z M 2 D s I Z M U g J 8 p g k m k u l b L T L G E h P Q c Z V 0 C M 7 q y + u k U 6 8 5 l 7 X G f a P S v M n j K K J T d I a q y E F X q I n u U A u 1 E U F T 9 I x e 0 Z u R G S / G u / G x b C 0 Y + c w J + g P j 8 w e o F 5 Q z < / l a t e x i t > x pa(2) 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " H Y s 7 G n Q z Q s X U R o 7 7 Q g T w k H j f D L 8 = " > A A A B + 3 i c b V D L S s N A F J 3 U V 6 2 v W J d u B o t Q N y X R o i 6 L b l x W s A 9 o Y 5 h M J + 3 Q y Y O Z G 2 k J + R U 3 L h R x 6 4 + 4 8 2 + c t l l o 6 4 E L h 3 P u 5 d 5 7 v F h w B Z b 1 b R T W 1 j c 2 t 4 r b p Z 3 d v f 0 D 8 7 D c V l E i K W v R S E S y 6 x H F B A 9 Z C z g I 1 o 0 l I 4 E n W M c b 3 8 7 8 z h O T i k f h A 0 x j 5 g R k G H K f U w J a c s 3 y x L U f 0 z 6 w C a Q x y a o X Z 5 l r V q y a N Q d e J X Z O K i h H 0 z W / + o O I J g E L g Q q i V M + 2 Y n B S I o F T w b J S P 1 E s J n R M h q y n a U g C p p x 0 f n u G T 7 U y w H 4 k d Y W A 5 + r v i Z Q E S k 0 D T 3 c G B E Z q 2 Z u J / 3 m 9 B P x r J + V h n A A L 6 W K R n w g M E Z 4 F g Q d c M g p i q g m h k u t b M R 0 R S S j o u E o 6 B H v 5 5 V X S P q / Z l 7 X 6 f b 3 S u M n j K K J j d I K q y E Z X q I H u U B O 1 E E U T 9 I x e 0 Z u R G S / G u / Gx a C 0 Y + c w R + g P j 8 w e p n Z Q 0 < / l a t e x i t >x pa(3) 1< l a t e x i t s h a 1 _ b a s e 6 4 = " h 9 / h G x Y J W j q j b C S 8 Q S J l 6 H R 8 O q k = " > C r x M 1 J G e V o + P Z X r x / R J G Q S q C B a d 1 0 n B i 8 l C j g V L C v 2 E s 1 i Q s d k y L q G S h I y 7 a X z 2 z N 8 Z p Q + H k T K l A Q 8 V 3 9 P p C T U e h o G p j M k M N L L 3 k z 8 z + s m M L j 2 U i 7 j B J i k i 0 W D R G C I 8 C w I 3 O e K U R B T Q w h V 3 N y K 6 Y g o Q s H E V T Q h u M s v r 5 L W R d W 9 r N b u a + X 6 T R 5 H A Z 2 g U 1 R B L r p C d X SH G q i J K J q g Z / S K 3 q z M e r H e r Y 9 F 6 5 q V z x y j P 7 A + f w C r I 5 Q 1 < / l a t e x i t >x pa(4) 1< l a t e x i t s h a 1 _ b a s e 6 4 = " U m y 0 6 z 3 4f x i k S j i 0 j Q h U o E I B 8 B s = " > A A A B 8 H i c b V B N S w M x E J 3 1 s 9 a v q k c v w S L U S 9 k t R T 0 W v X i s Y D + k X U s 2 z b a h S X Z J s m J Z + i u 8 e F D E q z / H m / / G t N 2 D t j 4 Y e L w 3 w 8 y 8 I O Z M G 9 f 9 d l Z W 1 9 Y 3 N n N b + e 2 d 3 b 3 9 w s F h U 0 e J I r R B I h 6 p d o A 1 5 U z S h m G G 0 3 a s K B Y B p 6 1 g d D 3 1 W 4 9 U a R b J O z O O q S / w Q L K Q E W y s d P / U q z y k J e 9 s 0 i s U 3 b I 7 A 1 o m X k a K k K H e K 3 x 1 + x F J B J W G c K x 1 x 3 N j 4 6 d Y G U Y 4 n e S 7 i a Y x J i M 8 o B 1 L J R Z U + + n s 4 A k 6 t U o f h Z G y J Q 2 a q b 8 n U i y 0 H o v A d g p s h n r R m 4 r / e Z 3 E h J d + y m S c G C r J f F G Y c G Q i N P 0 e 9 Z m i x P C x J Z g o Z m 9 F Z I g V J s Z m l L c h e I s v L 5 N m p e y d l 6 u 3 1 W L t K o s j B 8 d w A i X w 4 A J q c A N 1 a A A B A c / w C m + O c l 6 c d + d j 3 r r i Z D N H 8 A f O 5 w / E O I + + < / l a t e x i t >x(1) 2< l a t e x i t s h a 1 _ b a s e 6 4 = " 2 P q 9 E l 2 6 P g X 4EQUATION< l a t e x i t s h a 1 _ b a s e 6 4 = " R P x pa(4) 2I m Q G 6 Z 2 X f s 2 Y A Y q t L x j U 0 T y U s = " > A A A B + 3 i c b V B N S 8 N A E N 3 U r 1 q / Y j 1 6 C R a h X k p S i n o s e v F Y w X 5 A G 8 N m u 2 m X b j Z h d y I t I X / F i w d F v P p H v P l v 3 L Y 5 a O u D g c d 7 M 8 z M 8 2 P O F N j 2 t 1 H Y 2 N z a 3 i n u l v b 2 D w 6 P z O N y R 0 W J J L R N I h 7 J n o 8 V 5 U z Q N j D g t B d L i k O f 0 6 4 / u Z 3 7 3 S c q F Y v E A 8 x i 6 o Z 4 J F j A C A Y t e W Z 5 6 t U f 0 w H Q K a Q x z q q N i 8 w z K 3 b N X s B a J 0 5 O K i h H y z O / B s O I J C E V Q D h W q u / Y M b g p l s A I p 1 l p k C g a Y z L B I 9 r X V O C Q K j d d 3 J 5 Z 5 1 o Z W k E k d Q m w F u r v i R S H S s 1 C X 3 e G G M Z q 1 Z u L / 3 n 9 B I J r N 2 U i T o A K s l w U J N y C y J o H Y Q 2 Z p A T 4 T B N M J N O 3 W m S M< l a t e x i t s h a 1 _ b a s e 6 4 = " 3 2 0V P k l R g E W h B 8 h n n E i R h 3 x n 5 c E = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 m k q M e i F 4 8 V 7 Q e 0 o W y 2 k 3 b p Z h N 2 N 0 I J / Q l e P C j i 1 V / k z X / j t s 1 B W x 8 M P N 6 b Y W Z e k A i u j e t + O 4 W 1 9 Y 3 N r e J 2 a W d 3 b / + g f H j U 0 n G q G D Z Z L G L V C a h G w S U 2 D T c C O 4 l C G g U C 2 8 H 4 d u a 3 n 1 B p H s t H M 0 n Q j + h Q 8 p A z a q z 0 Q P t e v 1 x x q + 4 c Z J V 4 O a l A j k a / / N U b x C y N U B o m q N Z d z 0 2 M n 1 F l O B M 4 L f V S j Q l l Y z r E r q W S R q j 9 b H 7 q l J x Z Z U D C W N m S h s z V 3 x M Z j b S e R I H t j K g Z 6 W V v J v 7 n d V M T X v s Z l 0 l q U L L F o j A V x M R k 9 j c Z c I X M i I k l l C l u b y V s R B V l x q Z T s i F 4 y y + v k t Z F 1 b u s 1 u 5 r l f p N H k c R T u A U z s G D K 6 j D H T S g C Q y G 8 A y v 8 O Y I 5 8 V 5 d z 4 W r Q U n n z m G P 3 A + f w D r h Y 2 S < / l a t e x i t > a 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " W x k Z s 5 x R s 3 8 l J D 4 l 9 + F X g H m 0 H f I = " > A A A B 6 n i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L B b B U 0 l K U Y 9 F L x 4 r 2 l p o Q 9 l s J + 3 S z S b s b o Q S + h O 8 e F D E q 7 / I m / / G b Z u D t j 4 Y e L w 3 w 8 y 8 I B F c G 9 f 9 d g p r 6 x u b W 8 X t 0 s 7 u 3 v 5 B + f C o r e N U M W y x W M S q E 1 C N g k t s G W 4 E d h K F N A o E P g b j m 5 n / + I R K 8 1 g + m E m C f k S H k o e c U W O l e 9 q v 9 c s V t + r O Q V a J l 5 M K 5 G j 2 y 1 + 9 Q c z S C K V h g m r d 9 d z E + B l V h j O B 0 1 I v 1 Z h Q N q Z D 7 F o q a Y T a z + a n T s m Z V Q Y k j J U t a c h c / T 2 R 0 U j r S R T Y z o i a k V 7 2 Z u J / X j c 1 4 Z W f c Z m k B i V b L A p T Q U x M Z n + T A V f I j J h Y Q p n i 9 l b C R l R R Z m w 6 J R u C t / z y K m n X q t 5 F t X 5 X r z S u 8 z i K c A K n c A 4 e X E I D b q E J L W A w h G d 4 h T d H O C / O u / O x a C 0 4 + c w x / I H z + Q P t C Y 2 T < / l a t e x i t > a 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " 2 9 u d D u R t 3 V B 1 W p J u Y c h S M w k P 7 Q g = " > A A A C G H i c b Z C 5 T g M x E I a 9 n C F c A U q a F R F S a M I u Q k C J o K E M E j m k J K y 8 z m y w 8 N o r e x a I V v s Y N L w K D Q U I 0 a b j b X C O g m s k S 5 / + f 0 b j + c N E c I O e 9 + n M z M 7 N L y w W l o r L K 6 t r 6 6 W N z Y Z R q W Z Q Z 0 o o 3 Q q p A c E l 1 J G j g F a i g c a h g G Z 4 e z 7 y m 3 e g D V f y C g c J d G P a l z z i j K K V g t J + J 5 U 9 6 w N m H a F k X 0 C E V G t 1 n 2 c y C K + z i r + X V x 4 C f 0 J 7 e V A q e 1 V v X O 5 f 8 K d Q J t O q B a V h p 6 d Y G o N E J q g x b d 9 L s J t R j Z w J y I u d 1 E B C 2 S 3 t Q 9 u i p D G Y b j Y + L H d 3 r d J z I 6 X t k + i O 1 e 8 T G Y 2 N G c S h 7 Y w p 3 p j f 3 k j 8 z 2 u n G J 1 0 M y 6 T F E G y y a I o F S 4 q d 5 S S 2 + M a G I q B B c o 0 t 3 9 1 2 Q 3 V l K H N q m h D 8 H + f / B c a B 1 X / q H p 4 e V g + P Z v G U S D b Z I d U i E + O y S m 5 I D V S J 4 w 8 k m f y S t 6 c J + f F e X c + J q 0 z z n R m i / w o Z / g F E B u g W g = = < / l a t e x i t > n (1) b (x (1) 1 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " 2 t D 7 C C T 0 a S K A a 1 S O Q c E G 1 h E 1 x a g = " > A A A C G H i c b Z A 9 T 8 M w E I Y d v i l f B U a W i A q p X U q C E D A i W B i L R A t S W y L H v R Q L x 4 7 s C 1 B F + R k s / B U W B h B i 7 c a / w f 0 Y o O U k S 4 / e 9 0 7 n e 8 N E c I O e 9 + 3 M z M 7 N L y w u L R d W V t f W N 4 q b W w 2 j U s 2 g z p R Q + i a k B g S X U E e O A m 4 S D T Q O B V y H 9 + c D / / o B t O F K X m E v g X Z M u 5 J H n F G 0 U l D c b 6 W y Y 3 3 A r C W U 7 A q I k G q t H v N M B u F t V v Y r e f k p 8 C 0 d V P J K H h R L X t U b l j s N / h h K Z F y 1 o N h v d R R L Y 5 D I B D W m 6 X s J t j O q k T M B e a G V G k g o u 6 d d a F q U N A b T z o a H 5 e 6 e V T p u p L R 9 E t 2 h + n s i o 7 E x v T i 0 n T H F O z P p D c T / v G a K 0 U k 7 4 z J J E S Q b L Y p S 4 a J y B y m 5 H a 6 B o e h Z o E x z + 1 e X 3 V F N G d q s C j Y E f / L k a W g c V P 2 j 6 u H l Y e n 0 b B z H E t k h u 6 R M f H J M T s k F q Z E 6 Y e S Z v J J 3 8 u G 8 O G / O p / M 1 a p 1 x x j P b 5 E 8 5 / R 8 R o 6 B b < / l a t e x i t > n ( 1 ) b ( x ( 2 ) 1 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " e x A z v 5 1 r Q + B W q m 3 I q k K q R i t R c + E = " > A A A C G H i c b Z A 9 T 8 M w E I Y d P k v 5 K j C y R F R I 7 V K S q g L G C h Z G k C g g t S V y 3 E t r 1 b E j + w J U U X 4 G C 3 + F h Q G E W N n 4 N 7 i l A 1 8 n W X r 0 v n c 6 3 x s m g h v 0 v A 9 n Z n Z u f m G x s F R c X l l d W y 9 t b F 4 Y l W o G L a a E 0 l c h N S C 4 h B Z y F H C V a K B x K O A y H B 6 P / c s b 0 I Y r e Y 6 j B L o x 7 U s e c U b R S k F p r 5 P K n v U B s 4 5 Q s i 8 g Q q q 1 u s 0 z G Y T X W a V R z S t 3 g W + p X s 2 r e V A q e z V v U u 5 f 8 K d Q J t M 6 D U r v n Z 5 i a Q w S m a D G t H 0 v w W 5 G N X I m I C 9 2 U g M J Z U P a h 7 Z F S W M w 3 W x y W O 7 u W q X n R k r b J 9 G d q N 8 n M h o b M 4 p D 2 x l T H J j f 3 l j 8 z 2 u n G B 1 2 M y 6 T F E G y r 0 V R K l x U 7 j g l t 8 c 1 M B Q j C 5 R p b v / q s g H V l K H N q m h D 8 H + f / B c u 6 j V / v 9 Y 4 a 5 S b R 9 M 4 C m S b 7 J A K 8 c k B a Z I T c k p a h J F 7 8 k i e y Y v z 4 D w 5 r 8 7 b V + u M M 5 3 Z I j / K e f 8 E F l m g X g = = < / l a t e x i t > n (4 ) b ( x (2 ) 1 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " D b I 8 w 2 V z M 2 B b N 6 r J z 2 p p q A o i r Y c = " > A A A C G H i c b Z C 7 T s M w F I Y d r q X c C o w s E R V S u 5 S k q o C x g o W x S P Q i t S V y X K e 1 6 t i R f Q J U U R 6 D h V d h Y Q A h 1 m 6 8 D e 5 l g J Y j W f r 0 / + f o + P x + x J k G x / m 2 V l b X 1 j c 2 M 1 v Z 7 Z 3 d v f 3 c w W F D y 1 g R W i e S S 9 X y s a a c C V o H B p y 2 I k V x 6 H P a 9 I f X E 7 / 5 Q J V m U t z B K K L d E P c F C x j B Y C Q v d 9 a R E 5 t C 0 u F S 9 B X r D w A r J R / T R H j B f V J w i 2 n h y X M N l Y t p M f V y e a f k T M t e B n c O e T S v m p c b d 3 q S x C E V Q D j W u u 0 6 E X Q T r I A R T t N s J 9 Y 0 w m S I + 7 R t U O C Q 6 m 4 y P S y 1 T 4 3 S s w O p z B N g T 9 X f E w k O t R 6 F v u k M M Q z 0 o j c R / / P a M Q S X 3 Y S J K A Y q y G x R E H M b p D 1 J y e 4 x R Q n w k Q F M F D N / t c k A K 0 z A h J U 1 I b i L J y 9 D o 1 x y z 0 u V 2 0 q + e j W P I 4 O O 0 Q k q I B d d o C q 6 Q T V U R w Q 9 o 1 f 0 j j 6 s F + v N + r S + Z q 0 r 1 n z m C P 0 p a / w D N E i g c A = = < / l a t e x i t > ! n (1 ) f ( x (2 ) 1 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " G x f s s t k 7 0 + e p W K E S 3 f e B H V Q 1 F e k = " > A A A C G H i c b Z C 7 T s M w F I a d c i v l V m B k i a i Q 2 q U k q A L G C h b G I t G L 1 J b I c Z 3 W q m N H 9 g l Q R X k M F l 6 F h Q G E W L v x N r i X A V q O Z O n T / 5 + j 4 / P 7 E W c a H O f b y q y s r q 1 v Z D d z W 9 s 7 u 3 v 5 / Y O G l r E i t E 4 k l 6 r l Y 0 0 5 E 7 Q O D D h t R Y r i 0 O e 0 6 Q + v J 3 7 z g S r N p L i D U U S 7 I e 4 L F j C C w U h e / r Q j J z a F p M O l 6 C v W H w B W S j 6 m i f C C + 6 T o l t L i k + f O q J R 6 + Y J T d q Z l L 4 M 7 h w K a V 8 3 L j z s 9 S e K Q C i A c a 9 1 2 n Q i 6 C V b A C K d p r h N r G m E y x H 3 a N i h w S H U 3 m R 6 W 2 i d G 6 d m B V O Y J s K f q 7 4 k E h 1 q P Q t 9 0 h h g G e t G b i P 9 5 7 R i C y 2 7 C R B Q D F W S 2 K I i 5 D d K e p G T 3 m K I E + M g A J o q Z v 9 p k g B U m Y M L K m R D c x Z O X o X F W d s / L l d t K o X o 1 j y O L j t A x K i I X X a A q u k E 1 V E c E P a N X 9 I 4 + r B f r z f q 0 v m a t G W s + c 4 j + l D X + A T L A o G 8 = < / l a t e x i t > ! n (1) f (x (1) 1 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " r 5 k L a 5 K s p W v r / B c l E Q t E X g T N o j Q = " > A A A C I H i c b V B N b 9 N A E F 2 X r 5 J S M H D k s i K q l F w i u 6 o a j l F 7 6 b F I p I k U B 2 u 9 G S e r r H e t 3 T F t t P J P 4 d K / 0 g s H E G p v 8 G v Y f B w g 4 U k j P b 0 3 o 5 l 5 W S m F x S j 6 F e w 9 e v z k 6 b P 9 5 4 2 D F 4 c v X 4 W v 3 1 x Z X R k O f a 6 l N s O M W Z B C Q R 8 F S h i W B l i R S R h k 8 / O l P / g C x g q t P u G i h H H B p k r k g j P 0 U h p 2 k 0 p N v A / o E q n V V E K O z B h 9 X b s i z V r O 3 d R p / N m 5 B O E G a c n q V t y u 2 3 W d h s 2 o E 6 1 A d 0 m 8 I U 2 y w W U a P i Q T z a s C F H L J r B 3 F U Y l j x w w K L q F u J J W F k v E 5 m 8 L I U 8 U K s G O 3 e r C m R 1 6 Z 0 F w b X w r p S v 1 7 w r H C 2 k W R + c 6 C 4 c x u e 0 v x f 9 6 o w v z D 2 A l V V g i K r x f l l a S o 6 T I t O h E G O M q F J 4 w b 4 W + l f M Y M 4 + g z a / g Q 4 u 2 X d 8 n V c S c + 7 Z x 8 P G n 2 z j Z x 7 J N 3 5 D 1 p k Z h 0 S Y 9 c k E v S J 5 x 8 J X f k O / k R 3 A b f g p / B / b p 1 L 9 j M v C X / I P j 9 B y 2 w p M s = < / l a t e x i t > mb(x pa(1) 1 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " q E 5 K r d c J u 9 l 5 6 s O x U S Q C s r d A B o w = " > A A A C I H i c b V B N b 9 N A E F 2 n 0 J Y A J Y U j l x V R p e Q S 2 V F F O V b l w r F I p I k U u 9 Z 6 P U 5 X X e 9 a u 2 P a a O W f w o W / w q U H E I J b + 2 v Y f B w g 4 U k j P b 0 3 o 5 l 5 W S W F x T C 8 D 1 o 7 j x 7 v 7 u 0 / a T 9 9 9 v z g R e f w 5 Y X V t e E w 4 l p q M 8 m Y B S k U j F C g h E l l g J W Z h H F 2 / X 7 h j z + D s U K r T z i v I C n Z T I l C c I Z e S j s n c a 1 y 7 w O 6 W G o 1 k 1 A g M 0 b f N K 5 M s 5 5 z t 0 0 6 v H Q u R r h F W r G m F / W b f t O k n W 4 4 C J e g 2 y R a k y 5 Z 4 z z t / I 5 z z e s S F H L J r J 1 G Y Y W J Y w Y F l 9 C 0 4 9 p C x f g 1 m 8 H U U 8 V K s I l b P t j Q I 6 / k t N D G l 0 K 6 V P + e c K y 0 d l 5 m v r N k e G U 3 v Y X 4 P 2 9 a Y / E u c U J V N Y L i q 0 V F L S l q u k i L 5 s I A R z n 3 h H E j / K 2 U X z H D O P r M 2 j 6 E a P P l b X I x H E R v B 8 c f j 7 u n Z + s 4 9 s l r 8 o b 0 S E R O y C n 5 Q M 7 J i H D y h X w j 3 8 m P 4 G t w F / w M f q 1 a W 8 F 6 5 h X 5 B 8 H D H y 9 H p M w = < / l a t e x i t > mb(x pa(1) 2 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " 6 9 t n 8 p 2 Y z L W B Y f u Y b G j x e f M A K n E = " > A A A C F n i c b V A 9 S w N B E N 3 z 2 / g V t b Q 5 D E I s D H c i a i n a W E Y w U U j i s b e Z i 4 t 7 u 8 f u n B q W + x U 2 / h U b C 0 V s x c 5 / 4 y a m 8 O v B w O O 9 G W b m x Z n g B o P g w x s b n 5 i c m p 6 Z L c 3 N L y w u l Z d X m k b l m k G D K a H 0 e U w N C C 6 h g R w F n G c a a B o L O I u v j g b + 2 T V o w 5 U 8 x X 4 G n Z T 2 J E 8 4 o + i k q L z V z m X X + Y C 2 L Z T s C U i Q a q 1 u C p t G c d X a 2 y L a v r D V c L P Y L I q o X A l q w R D + X x K O S I W M U I / K 7 + 2 u Y n k K E p m g x r T C I M O O p R o 5 E 1 C U 2 r m B j L I r 2 o O W o 5 K m Y D p 2 + F b h b z i l 6 y d K u 5 L o D 9 X v E 5 a m x v T T 2 H W m F C / N b 2 8 g / u e 1 c k z 2 O 5 b L L E e Q 7 G t R k g s f l T / I y O 9 y D Q x F 3 x H K N H e 3 + u y S a s r Q J V V y I Y S / X / 5 L m t u 1 c L e 2 c 7 J T O T g c x T F D 1 s g 6 q Z K Q 7 J E D c k z q p E E Y u S M P 5 I k 8 e / f e o / f i v X 6 1 j n m j m V X y A 9 7 b J 8 0 o o F 4 = < / l a t e x i t > mb(x (1) 2 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " s r z I d G + N x B r L E k s C X k Q P 3 w a 2 v d 4 = " > A A A C F n i c b V A 9 S w N B E N 3 z 2 / g V t b Q 5 D E I s D H c a 1 F K 0 s V Q w K i T x 2 N v M x c W 9 3 W N 3 T g 3 L / Q o b / 4 q N h S K 2 Y u e / c R N T + P V g 4 P H e D D P z 4 k x w g 0 H w 4 Y 2 M j o 1 P T E 5 N l 2 Z m 5 + Y X y o t L p 0 b l m k G D K a H 0 e U w N C C 6 h g R w F n G c a a B o L O I u v D v r + 2 T V o w 5 U 8 w V 4 G 7 Z R 2 J U 8 4 o + i k q L z R y m X H + Y C 2 J Z T s C k i Q a q 1 u C p t G c d X a 2 y L a u r D V c L 1 Y L 4 q o X A l q w Q D + X x I O S Y U M c R S V 3 1 s d x f I U J D J B j W m G Q Y Z t S z V y J q A o t X I D G W V X t A t N R y V N w b T t 4 K 3 C X 3 N K x 0 + U d i X R H 6 j f J y x N j e m l s e t M K V 6 a 3 1 5 f / M 9 r 5 p j s t i 2 X W Y 4 g 2 d e i J B c + K r + f k d / h G h i K n i O U a e 5 u 9 d k l 1 Z S h S 6 r k Q g h / v / y X n G 7 W w u 1 a / b h e 2 d s f x j F F V s g q q Z K Q 7 J A 9 c k i O S I M w c k c e y B N 5 9 u 6 9 R + / F e / 1 q H f G G M 8 v k B 7 y 3 T 8 6 1 o F 8 = < / l a t e x i t > mb(x (1)) < l a t e x i t s h a 1 _ b a s e 6 4 = " k 7 0 s A 8 f M 6 S V 5 b t e s j l VI I X 0 T Y D g = " > A A A C F n i c b V A 9 S w N B E N 3 z 2 / g V t b Q 5 D E I s D H d R 1 F K 0 s V Q w K i T x 2 N v M x c W 9 3 W N 3 T g 3 L / Q o b / 4 q N h S K 2 Y u e / c R N T + P V g 4 P H e D D P z 4 k x w g 0 H w 4 Y 2 M j o 1 P T E 5 N l 2 Z m 5 + Y X y o t L p 0 b l m k G D K a H 0 e U w N C C 6 h g R w F n G c a a B o L O I u v D v r + 2 T V o w 5 U 8 w V 4 G 7 Z R 2 J U 8 4 o + i k q L z R y m X H + Y C 2 J Z T s C k i Q a q 1 u C p t G c d X a 2 y L a v L D V + n q x X h R R u R L U g g H 8 v y Q c k g o Z 4 i g q v 7 c 6 i u U p S G S C G t M M g w z b l m r k T E B R a u U G M s q u a B e a j k q a g m n b w V u F v + a U j p 8 o 7 U q i P 1 C / T 1 i a G t N L Y 9 e Z U r w 0 v 7 2 + + J / X z D H Z b V s u s x x B s q 9 F S S 5 8 V H 4 / I 7 / D N T A U P U c o 0 9 z d 6 r N L q i l D l 1 T J h R D + f v k v O a 3 X w u 3 a 1 v F W Z W 9 / G M c U W S G r p E p C s k P 2 y C E 5 I g 3 C y B 1 5 I E / k 2 b v 3 H r 0 X 7 / W r d c Q b z i y T H / D e P g H Q P q B g < / l a t e x i t > mb(x (2) ) < l a t e x i t s h a 1 _ b a s e 6 4 = " V I x l P N y a + Z A c P M e D 2 v O k U X v G V g U = " > A A A C F n i c b V A 9 S w N B E N 3 z 2 / g V t b Q 5 D E I s D H c h q K V o Y 6 l g V E j i s b e Z i 4 t 7 u 8 f u n B q W + x U 2 / h U b C 0 V s x c 5 / 4 y a m 8 O v B w O O 9 G W b m x Z n g B o P g w x s b n 5 i c m p 6 Z L c 3 N L y w u l Z d X T o 3 K N Y M m U 0 L p 8 5 g a E F x C E z k K O M 8 0 0 D Q W c B Z f H Q z 8 s 2 v Q h i t 5 g v 0 M O i n t S Z 5 w R t F J U X m r n c u u 8 w F t W y j Z E 5 A g 1 V r d F D a N 4 q q 1 t 0 V U v 7 D V + m a x W R R R u R L U g i H 8 v y Q c k Q o Z 4 S g q v 7 e 7 i u U p S G S C G t M K g w w 7 l m r k T E B R a u c G M s q u a A 9 a j k q a g u n Y 4 V u F v + G U r p 8 o 7 U q i P 1 S / T 1 i a G t N P Y 9 e Z U r w 0 v 7 2 B + J / X y j H Z 7 V g u s x x B s q 9 F S S 5 8 V P 4 g I 7 / L N T A U f U c o 0 9 z d 6 r N L q i l D l 1 T J h R D + f v k v O a 3 X w u 1 a 4 7 h R 2 d s f x T F D 1 s g 6 q Z K Q 7 J A 9 c k i O S J M w c k c e y B N 5 9 u 6 9 R + / F e / 1 q H f N G M 6 v k B 7 y 3 T 8 6 x o F 8 = < / l a t e x i t > mb(x (2) 2 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " B f g + l n o B C u F d 1 r z h z t t h i c S b 3 p g = " > A A A C H 3 i c b V B N S 8 N A E N 3 4 b f 2 q e v Q S L E K 9 l K Q U 9 S h 6 8 a h g V W h q 2 G w n d X G z G 3 Y n a l n y T 7 z 4 V 7 x 4 U E S 8 + W / c 1 h 7 8 e j D w e G + G m X l J L r j B I P j w J i a n p m d m 5 + Y r C 4 t L y y v V 1 b U z o w r N o M 2 U U P o i o Q Y E l 9 B G j g I u c g 0 0 S w S c J 9 e H Q / / 8 B r T h S p 7 i I I d u R v u S p 5 x R d F J c 3 Y k K 2 X M + o I 2 E k n 0 B K V K t 1 W 1 p s z i p W 3 t X x s 1 L G y H c o c 1 p W W 9 u l 9 t l G V d r Q S M Y w f 9 L w j G p k T G O 4 + p 7 1 F O s y E A i E 9 S Y T h j k 2 L V U I 2 c C y k p U G M g p u 6 Z 9 6 D g q a Q a m a 0 f / l f 6 W U 3 p + q r Q r i f 5 I / T 5 h a W b M I E t c Z 0 b x y v z 2 h u J / X q f A d K 9 r u c w L B M m + F q W F 8 F H 5 w 7 D 8 H t f A U A w c o U x z d 6 v P r q i m D F 1 k F R d C + P v l v + S s 2 Q h 3 G q 2 T V m 3 / Y B z H H N k g m 6 R O Q r J L 9 s k R O S Zt w s g 9 e S T P 5 M V 7 8 J 6 8 V + / t q 3 X C G 8 + s k x / w P j 4 B x u y k o w = = < / l a t e x i t > mb(xpa(2) 2 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " x T f p z 4 + h J j G p N P f l r e O H u 9 p u T C c = " > A A A C H 3 i c b V B N S 8 N A E N 3 4 b f 2 q e v Q S L E K 9 l E S K e h S 9 e F S w K j Q 1 b L a T d n G z G 3 Y n a l n y T 7 z 4 V 7 x 4 U E S 8 + W / c 1 h 7 8 e j D w e G + G m X l J L r j B I P j w J i a n p m d m 5 + Y r C 4 t L y y v V 1 b V z o w r N o M W U U P o y o Q Y E l 9 B C j g I u c w 0 0 S w R c J N d H Q / / i B r T h S p 7 h I I d O R n u S p 5 x R d F J c 3 Y 3 U 0 A a 0 k V C y p 3 m v j 1 R r d V v a L E 7 r 1 t 6 V c X h l I 4 Q 7 t D k t 6 + F 2 u V 2 W c b U W N I I R / L 8 k H J M a G e M k r r 5 H X c W K D C Q y Q Y 1 p h 0 G O H U s 1 c i a g r E S F g Z y y a 9 q D t q O S Z m A 6 d v R f 6 W 8 5 p e u n S r u S 6 I / U 7 x O W Z s Y M s s R 1 Z h T 7 5 r c 3 F P / z 2 g W m + x 3 L Z V 4 g S P a 1 K C 2 E j 8 o f h u V 3 u Q a G Y u A I Z Z q 7 W 3 3 W p 5 o y d J l V X A j h 7 5 f / k v O d R r j b a J 4 2 a w e H 4 z j m y A b Z J H U S k j 1 y Q I 7 J C W k R R u 7 J I 3 k m L 9 6 D 9 + S 9 e m 9 f r R P e e G a d / I D 3 8 Q n n B a S 2 < / l a t e x i t > ! mf (x pa(1) 1 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " T y l 2 F O m o m W q N P a + C 5 n y D 2 W G r D X E = " > A A A C F n i c b V B N S 8 N A E N 3 4 W e t X 1 a O X Y B H q w Z I U U Y + i F 4 8 V b C u 0 M W y 2 m 3 Z x s x t 2 J 2 p Z 8 i u 8 + F e 8 e F D E q 3 j z 3 7 i p P f j 1 Y O D x 3 g w z 8 6 K U M w 2 e 9 + F M T c / M z s 2 X F s q L S 8 s r q 5 W 1 9 b a W m S K 0 R S S X 6 i L C m n I m a A s Y c H q R K o q T i N N O d H V S + J 1 r q j S T 4 h x G K Q 0 S P B A s Z g S D l c L K b k 8 W N g X T 4 1 I M F B s M A S s l b 3 K T h H H N m N s 8 b F y a m r + T 7 + R 5 W K l 6 d W 8 M 9 y / x J 6 S K J m i G l f d e X 5 I s o Q I I x 1 p 3 f S + F w G A F j H C a l 3 u Z p i k m V 3 h A u 5 Y K n F A d m P F b u b t t l b 4 b S 2 V L g D t W v 0 8 Y n G g 9 S i L b m W A Y 6 t 9 e I f 7 n d T O I D w P D R J o B F e R r U Z x x F 6 R b Z O T 2 m a I E + M g S T B S z t 7 p k i B U m Y K M q 2 x D 8 3 y / / J e 1 G 3 d + v 7 5 3 t V Y + O J 3 G U 0 C b a Q j X k o w N 0 h E 5 R E 7 U Q Q X f o A T 2 h Z + f e e X R e n N e v 1 i l n M r O B f s B 5 + w T v o 6 B z < / l a t e x i t > ! mf (x (1) 2 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " 4 2 i / X / y n j 8 c x 1 a u r l / 3 V 5 G W L / z o = " > A A A C H 3 i c b V B N S 8 N A E N 3 4 b f 2 q e v Q S L E K 9 l E S K e h S 9 e F S w K j Q 1 b L a T d n G z G 3 Y n a l n y T 7 z 4 V 7 x 4 U E S 8 + W / c 1 h 7 8 e j D w e G + G m X l J L r j B I P j w J i a n p m d m 5 + Y r C 4 t L y y v V 1 b V z o w r N o M W U U P o y o Q Y E l 9 B C j g I u c w 0 0 S w R c J N d H Q / / i B r T h S p 7 h I I d O R n u S p 5 x R d F J c 3 Y 3 U 0 A a 0 k V C y p 3 m v j 1 R r d V v a L E 7 r 1 t 6 V 8 c 6 V j R D u 0 O a 0 r I f b 5 X Z Z x t V a 0 A h G 8 P + S c E x q Z I y T u P o e d R U r M p D I B D W m H Q Y 5 d i z V y J m A s h I V B n L K r m k P 2 o 5 K m o H p 2 N F / p b / l l K 6 f K u 1 K o j 9 S v 0 9 Y m h k z y B L X m V H s m 9 / e U P z P a x e Y 7 n c s l 3 m B I N n X o r Q Q P i p / G J b f 5 R o Y i o E j l G n u b v V Z n 2 r K 0 G V W c S G E v 1 / + S 8 5 3 G u F u o 3 n a r B 0 c j u O Y I x t k k 9 R J S P b I A T k m J 6 R F G L k n j + S Zv H g P 3 p P 3 6 r 1 9 t U 5 4 4 5 l 1 8 g P e x y f o m 6 S 3 < / l a t e x i t > ! mf (xpa(1) 2 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " P 4 6 Q F V e / V 8 b O v 5 / L 5 e 8 g 9 I M F G F 4 = " > A A A C F n i c b V B N S 8 N A E N 3 4 b f 2 q e v Q S L E I 9 W B I t 6 r H o x a O C V a G J Y b P d t I u b 3 b A 7 U c u S X + H F v + L F g y J e x Z v / x m 3 t Q V s f D D z e m 2 F m X p x x p s H z v p y J y a n p m d m 5 + d L C 4 t L y S n l 1 7 U L L X B H a J J J L d R V j T T k T t A k M O L 3 K F M V p z O l l f H P c 9 y 9 v q d J M i n P o Z T R M c U e w h B E M V o r K O 4 H s 2 x R M w K X o K N b p A l Z K 3 h U m j Z K q M f d F t H d t q v 5 2 s V 0 U U b n i 1 b w B 3 H H i D 0 k F D X E a l T + D t i R 5 S g U Q j r V u + V 4 G o c E K G O G 0 K A W 5 p h k m N 7 h D W 5 Y K n F I d m s F b h b t l l b a b S G V L g D t Q f 0 8 Y n G r d S 2 P b m W L o 6 l G v L / 7 n t X J I D k P D R J Y D F e R n U Z J z F 6 T b z 8 h t M 0 U J 8 J 4 l m C h m b 3 V J F y t M w E Z V s i H 4 o y + P k 4 v d m r 9 f q 5 / V K 4 2 j Y R x z a A N t o i r y 0 Q F q o B N 0 i p q I o A f 0 h F 7 Q q / P o P D t v z v t P 6 4 Q z n F l H f + B 8 f A P x M K B 0 < / l a t e x i t > ! mf (x (1) ) < l a t e x i t s h a 1 _ b a s e 6 4 = " d b n p i 4 g M u m p C Z C D g 4 R I P 0 d l v 2 b Q = " > A A A C H H i c b V D L S g M x F M 3 4 r P V V d e l m s A j t p s z U o i 6 L b l x W s F V o 6 5 B J M 2 1 o J h m S O 2 o J 8 y F u / B U 3 L h R x 4 0 L w b 0 w f C 1 8 H L p y c c y + 5 9 4 Q J Z x o 8 7 9 O Z m 1 9 Y X F r O r e R X 1 9 Y 3 N g t b 2 y 0 t U 0 V o k 0 g u 1 V W I N e V M 0 C Y w 4 P Q q U R T H I a e X 4 f B 0 7 F / e U K W Z F B c w S m g 3 x n 3 B I k Y w W C k o H H T k 2 K Z g O l y K v m L 9 A W C l 5 G 1 m R B B d m 1 K 1 n J W M u c s C 3 z 7 8 c l b O s q B Q 9 C r e B O 5 f 4 s 9 I E c 3 Q C A r v n Z 4 k a U w F E I 6 1 b v t e A l 2 D F T D C a Z b v p J o m m A x x n 7 Y t F T i m u m s m x 2 X u v l V 6 b i S V L Q H u R P 0 + Y X C s 9 S g O b W e M Y a B / e 2 P x P 6 + d Q n T c N U w k K V B B p h 9 F K X d B u u O k 3 B 5 T l A A f W Y K J Y n Z X l w y w w g R s Y H k b g v / 7 5 L + k V a 3 4 h 5 X a e a 1 Y P 5 n F k U O 7 a A + V k I + O U B 2 d o Q Z q I o L u 0 S N 6 R i / O g / P k v D p v 0 9 Y 5 Z z a z g 3 7 A + f g C C a y i i A = = < / l a t e x i t > ! n ( 2 ) f ( x ( 1 ) 1 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " z / i f V Q X 2 f f I 2 Z c y D y 3 A x g A V J T / Y = " > A A A C H H i c b V B N S w M x E M 3 6 b f 2 q e v S y W I T 2 U n a 1 q E f R i 0 c F q 0 J b l 2 w 6 W 4 P Z Z E l m 1 R L 2 h 3 j x r 3 j x o I g X D 4 L / x r T 2 4 N e D g Z f 3 Z s j M i z P B D Q b B h z c 2 P j E 5 N T 0 z W 5 q b X 1 h c K i + v n B q V a w Z N p o T S 5 z E 1 I L i E J n I U c J 5 p o G k s 4 C y + O h j 4 Z 9 e g D V f y B P s Z d F L a k z z h j K K T o v J W O 5 d d 5 w P a t l C y J y B B q r W 6 K a y M 4 g t b 3 a w V V W t v i y h 0 j 7 B W 1 I o i K l e C e j C E / 5 e E I 1 I h I x x F 5 b d 2 V 7 E 8 B Y l M U G N a Y Z B h x 1 K N n A k o S u 3 c Q E b Z F e 1 B y 1 F J U z A d O z y u 8 D e c 0 v U T p V 1 J 9 I f q 9 w l L U 2 P 6 a e w 6 U 4 q X 5 r c 3 E P / z W j k m u x 3 L Z Z Y j S P b 1 U Z I L H 5 U / S M r v c g 0 M R d 8 R y j R 3 u / r s k m r K 0 O V V c i G E v 0 / + S 0 4 3 6 + F 2 v X H c q O z t j + K Y I W t k n V R J S H b I H j k k R 6 R J G L k j D + S J P H v 3 3 q P 3 4 r 1 + t Y 5 5 o 5 l V 8 g P e + y f m p K J z < / l a t e x i t > n ( 2 ) b ( x ( 1 ) 1 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " 4 W L 3 M Y o m J A 9 2 V m K L p I h 4 P a z m A y E = " > A A A C H H i c b V D L S g M x F M 3 4 t r 6 q L t 0 M F q H d l B k t 6 r L o x q W C f U B b h 0 y a a Y O Z Z E j u q C X M h 7 j x V 9 y 4 U M S N C 8 G / M X 0 s t P X A h Z N z 7 i X 3 n j D h T I P n f T t z 8 w u L S 8 s r q 7 m 1 9 Y 3 N r f z 2 T l 3 L V B F a I 5 J L 1 Q y x p p w J W g M G n D Y T R X E c c t o I b 8 + H f u O O K s 2 k u I Z B Q j s x 7 g k W M Y L B S k H + q C 2 H N g X T 5 l L 0 F O v 1 A S s l 7 z M j g u j G F C u l r G j M Q x b 4 9 n F Y y k p Z F u Q L X t k b w Z 0 l / o Q U 0 A S X Q f 6 z 3 Z U k j a k A w r H W L d 9 L o G O w A k Y 4 z X L t V N M E k 1 v c o y 1 L B Y 6 p 7 p j R c Z l 7 Y J W u G 0 l l S 4 A 7 U n 9 P G B x r P Y h D 2 x l j 6 O t p b y j + 5 7 V S i E 4 7 h o k k B S r I + K M o 5 S 5 I d 5 i U 2 2 W K E u A D S z B R z O 7 q k j 5 W m I A N L G d D 8 K d P n i X 1 w 7 J / X K 5 c V Q r V s 0 k c K 2 g P 7 a M i 8 t E J q q I L d I l q i K B H 9 I x e 0 Z v z 5 L w 4 7 8 7 H u H X O m c z s o j 9 w v n 4 A D m G i i w = = < / l a t e x i t > ! n ( 4 ) f ( x ( 2 ) 1 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " Q c / v p k L 8 q m Q 9 z l r + L 4 8 y e e X c 8 3 k = " > A A A C H H i c b V B N T w I x E O 3 6 i f i F e v S y k Z j A h e w i U Y 9 E L x 4 x E T Q B 3 H R L F x q 6 7 a a d V U m z P 8 S L f 8 W L B 4 3 x 4 s H E f 2 N B D i q + Z J L X 9 2 b S m R c m n G n w v E 9 n b n 5 h c W k 5 t 5 J f X V v f 2 C x s b b e 0 T B W h T S K 5 V F c h 1 p Q z Q Z v A g N O r R F E c h 5 x e h s P T s X 9 5 Q 5 V m U l z A K K H d G P c F i x j B Y K W g c N C R Y 5 u C 6 X A p + o r 1 B 4 C V k r e Z E U F 0 b U r V c l Y y 5 i 4 L q v b h l 7 N y l g W F o l f x J n B n i T 8 l R T R F I y i 8 d 3 q S p D E V Q D j W u u 1 7 C X Q N V s A I p 1 m + k 2 q a Y D L E f d q 2 V O C Y 6 q 6 Z H J e 5 + 1 b p u Z F U t g S 4 E / X n h M G x 1 q M 4 t J 0 x h o H + 6 4 3 F / 7 x 2 C t F x 1 z C R p E A F + f 4 o S r k L 0 h 0 n 5 f a Y o g T 4 y B J M F L O 7 u m S A F S Z g A 8 v b E P y / J 8 + S V r X i H 1 Z q 5 7 V i / W Q a R w 7 t o j 1 U Q j 4 6 Q n V 0 h h q o i Q i 6 R 4 / o G b 0 4 D 8 6 T 8 + q 8 f b f O O d O Z H f Q L z s c X C z m i i Q = = < / l a t e x i t > ! n ( 2 ) f ( x ( 1 ) 2 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " W o y 8 y c 6 E 0 k M 8 h f y i o k O U j i B v K L s = " > A A A C H H i c b V B N T w I x E O 3 6 i f i F e v S y k Z j A h e w i U Y 9 E L x 4 x E T Q B 3 H R L F x q 6 7 a a d V U m z P 8 S L f 8 W L B 4 3 x 4 s H E f 2 N B D i q + Z J L X 9 2 b S m R c m n G n w v E 9 n b n 5 h c W k 5 t 5 J f X V v f 2 C x s b b e 0 T B W h T S K 5 V F c h 1 p Q z Q Z v A g N O r R F E c h 5 x e h s P T s X 9 5 Q 5 V m U l z A K K H d G P c F i x j B Y K W g c N C R Y 5 u C 6 X A p + o r 1 B 4 C V k r e Z E U F 0 b U q 1 c l Y y 5 i 4 L q v Z R L W f l L A s K R a / i T e D O E n 9 K i m i K R l B 4 7 / Q k S W M q g H C s d d v 3 E u g a r I A R T r N 8 J 9 U 0 w W S I + 7 R t q c A x 1 V 0 z O S 5 z 9 6 3 S c y O p b A l w J + r P C Y N j r U d x a D t j D A P 9 1 x u L / 3 n t F K L j r m E i S Y E K 8 v 1 R l H I X p D t O y u 0 x R Q n w k S W Y K G Z 3 d c k A K 0 z A B p a 3 I f h / T 5 4 l r W r F P 6 z U z m v F + s k 0 j h z a R X u o h H x 0 h O r o D D V Q E x F 0 j x 7 R M 3 p x H p w n 5 9 V 5 + 2 6 d c 6 Y z O + g X n I 8 v D + 6 i j A = = < / l a t e x i t > ! n (4 ) f ( x (2 ) 2 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " g a y l 6 0 2 b Y t s K J N G B E p 3 U K v + o a W s = " > A A A C H H i c b V D L S g M x F M 3 4 r P V V d e l m s A h 1 U 2 a 0 q M u i G 5 c V 7 A P a O m T S T B v M J E N y R y 1 h P s S N v + L G h S J u X A j + j e l j o d U D F 0 7 O u Z f c e 8 K E M w 2 e 9 + X M z S 8 s L i 3 n V v K r a + s b m 4 W t 7 Y a W q S K 0 T i S X q h V i T T k T t A 4 M O G 0 l i u I 4 5 L Q Z 3 p y P / O Y t V Z p J c Q X D h H Z j 3 B c s Y g S D l Y L C U U e O b A q m w 6 X o K 9 Y f A F Z K 3 m V G B N G 1 K f k H W c m Y + y w 4 n D w O s i w o F L 2 y N 4 b 7 l / h T U k R T 1 I L C R 6 c n S R p T A Y R j r d u + l 0 D X Y A W M c J r l O 6 m m C S Y 3 u E / b l g o c U 9 0 1 4 + M y d 9 8 q P T e S y p Y A d 6 z + n D A 4 1 n o Y h 7 Y z x j D Q s 9 5 I / M 9 r p x C d d g 0 T S Q p U k M l H U c p d k O 4 o K b f H F C X A h 5 Z g o p j d 1 S U D r D A B G 1 j e h u D P n v y X N A 7 L / n G 5 c l k p V s + m c e T Q L t p D J e S j E 1 R F F 6 i G 6 o i g B / S E X t C r 8 + g 8 O 2 / O + 6 R 1 z p n O 7 K B f c D 6 / A Q m j o o g = < / l a t e x i t > ! mf (x pa(2) 1 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " P j T d 7 l Z x U 6 5 k F m C z I 0 6 g s m p o v f w = " > A A A C I H i c b V B N S 8 N A E N 3 4 b f 2 q e v Q S L E K 9 l E S K e h S 9 e F S w K j Q 1 b L a T u r j Z D b s T t S z 5 K V 7 8 K 1 4 8 K K I 3 / T V u a w 9 + P R h 4 v D f D z L w k F 9 x g E L x 7 Y + M T k 1 P T M 7 O V u f m F x a X q 8 s q p U Y V m 0 G J K K H 2 e U A O C S 2 g h R w H n u Q a a J Q L O k q u D g X 9 2 D d p w J U + w n 0 M n o z 3 J U 8 4 o O i m u 7 k S F 7 D o f 0 E Z C y Z 6 A F K n W 6 q a 0 W Z z U r b 0 t 4 / D C R g i 3 a H N a 1 r c 2 y 8 2 y r M T V W t A I h v D / k n B E a m S E o 7 j 6 F n U V K z K Q y A Q 1 p h 0 G O X Y s 1 c i Z g L I S F Q Z y y q 5 o D 9 q O S p q B 6 d j h g 6 W / 4 Z S u n y r t S q I / V L 9 P W J o Z 0 8 8 S 1 5 l R v D S / v Y H 4 n 9 c u M N 3 t W C 7 z A k G y r 0 V p I X x U / i A t v 8 s 1 M B R 9 R y j T 3 N 3 q s 0 u q K U O X 2 S C E 8 P f L f 8 n p V i P c b j S P m 7 W 9 / V E c M 2 S N r J M 6 C c k O 2 S O H 5 I i 0 C C N 3 5 I E 8 k W f v 3 n v 0 X r z X r 9 Y x b z S z S n 7 A + / g E D 8 y k t g = = < / l a t e x i t > mb(x pa(2) 1 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " W O w V m g V v + f J H B 6 f n v b m h 4 n r c D i Q = " > A A A C E n i c d V B N S y N B F O z x Y 4 1 Z X a M e v T Q G I b m E H j N E c w v u x a O K U S H J h p 7 O G 2 3 s + a D 7 j R i G + Q 1 e / C t 7 8 a C I V 0 / e / D f 2 a A Q V L W g o q u r x + p W f K G m Q s W d n a n p m 9 t d c a b 7 8 e 2 H x z 1 J l e e X I x K k W 0 B W x i v W J z w 0 o G U E X J S o 4 S T T w 0 F d w 7 J / / L f z j C 9 B G x t E h j h M Y h P w 0 k o E U H K 0 0 r N T h X 9 Z X N j / i 9 K C W 9 f 2 A X u Z D l 1 o V 4 R K z h O e 1 Z j 2 v 5 + V h p c o a r N 1 s N x l l D Y + 1 v N a 2 J Y x 5 7 U 2 P u p Y U q J I J 9 o a V p / 4 o F m k I E Q r F j e m 5 L M F B x j V K o S A v 9 1 M D C R f n / B R 6 l k Y 8 B D P I X k / K 6 Y Z V R j S I t X 0 R 0 l f 1 4 0 T G Q 2 P G o W + T I c c z 8 9 U r x O + 8 X o r B 9 i C T U Z I i R O J t U Z A q i j E t + q E j q U G g G l v C h Z b 2 r 1 S c c c 0 F 2 h a L E t 4 v p T + T o 8 2 G 2 2 p 4 + 1 6 1 s z O p o 0 T W y D q p E Z d s k Q 7 Z J X u k S w S 5 I v / J L b l z r p 0 b 5 9 5 5 e I t O O Z O Z V f I J z u M L 6 B i d A g = = < / l a t e x i t > e R(x pa(3) 1 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " v 0 l / 4 Q K 9 6 M Q D c L M C r 5 U B V A O E o h 8 = " > A A A C E n i c d V C 7 S g N B F J 3 1 b X x F L W 0 G g 5 A 0 Y V a X a D r R x l L F q J D E M D u 5 q 4 O z D 2 b u i m H Z b 7 D x V 2 w s F L G 1 s v N v n N U I K n p g 4 H D O u d y 5 x 0 + U N M j Y m z M y O j Y + M T k 1 X Z q Z n Z t f K C 8 u H Z s 4 1 Q J a I l a x P v W 5 A S U j a K F E Ba e J B h 7 6 C k 7 8 y 9 3 C P 7 k C b W Q c H e E g g W 7 I z y M Z S M H R S r 1 y D c 6 y j r L 5 P q e H 1 a z j B / Q 6 7 7 n U q g j X m C U 8 r 3 q 1 v J a X e u U K q 7 P m R n O D U V b 3 W M N r b F n C m N d c 9 6 h r S Y E K G W K / V 3 7 t 9 G O R h h C h U N y Y t s s S 7 G Z c o x Q K 8 l I n N Z B w c c n P o W 1 p x E M w 3 e z j p J y u W a V P g 1 j b F y H 9 U L 9 P Z D w 0 Z h D 6 N h l y v D C / v U L 8 y 2 u n G G x 1 M x k l K U I k P h c F q a I Y 0 6 I f 2 p c a B K q B J V x o a f 9 K x Q X X X K B t s S j h 6 1 L 6 P z l e r 7 u N u n f g V b Z 3 h n V M k R W y S q r E J Z t k m + y R f d I i g t y Q O / J A= " > A A A C E n i c d V C 7 S g N B F J 3 1 b X x F L W 0 G g 5 A 0 Y R K X a D r R x l L F q J D E M D u 5 q 0 N m H 8 z c F c O y 3 2 D j r 9 h Y K G J r Z e f f O K s R V P T A w O G c c 7 l z j x c r a Z C x N 2 d s f G J y a n p m t j A 3 v 7 C 4 V F x e O T F R o g W 0 R K Q i f e Z x A 0 q G 0 E K J C s 5 i D T z w F J x 6 g 7 3 c P 7 0 C b W Q U H u M w h m 7 A L 0 L p S 8 H R S r 1 i B c 7 T j r L 5 P q d H 5 b T j + f Q 6 6 9 W p V R G u M Y 1 5 V n Y r W S U r 9 I o l V m X N z e Y m o 6 z q s o b b 2 L a E M b d Z d 2 n N k h w l M s J B r / j a 6 U c i C S B E o b g x 7 R q L s Z t y j V I o y A q d x E D M x Y B f Q N v S k A d g u u n H S R n d s E q f + p G 2 L 0 T 6 o X 6 f S H l g z D D w b D L g e G l + e 7 n 4 l 9 d O 0 N / u p j K M E 4 R Q f C 7 y E 0 U x o n k / t C 8 1 C F R D S 7 j Q 0 v 6 V i k u u u U D b Y l 7 C 1 6 X 0 f 3 J S r 9 Y a V f f Q L e 3 s j u q Y I W t k n Z R J j W y R H b J P D k i L C H J D 7 s g D e X R u n X v n y X n + j I 4 5 o 5 l V 8 g P O y z v r O J 0 E < / l a t e x i t > e R(x pa(4) 2 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " c P z r a H 8 t d 0 7 o 7 6 t u s U s X g B M q V v 8 = " > A A A C E n i c d V C 7 S g N B F J 3 1 b X x F L W 0 G g 5 A 0 Y Z I s 0 X S i j a W K U S G J Y X Z y V w d n H 8 z c F c O y 3 2 D j r 9 h Y K G J r Z e f f O K s R V P T A w O G c c 7 l z j x c r a Z C x N 2 d s f G J y a n p m t j A 3 v 7 C 4 V F x e O T Z R o g W 0 R a Q i f e p x A 0 q G 0 E a J C k 5 j D T z w F J x 4 l 7 u 5 f 3 I F 2 s g o P M J h D L 2 A n 4 f S l 4 K j l f r F C p y l X W X z A 0 4 P y 2 n X 8 + l 1 1 q 9 T q y J c Y x r z r N y o Z J W s 0 C + W W J W 1 G q 0 G o 6 z q s q b b 3 L K E M b d V d 2 n N k h w l M s J + v / j a H U Q i C S B E o b g x n R q L s Z d y j V I o y A r d x E D M x S U / h 4 6 l I Q / A 9 N K P k z K 6 Y Z U B 9 S N t X 4 j 0 Q / 0 + k f L A m G H g 2 W T A 8 c L 8 9 n L x L 6 + T o L / V S 2 U Y J w i h + F z k J 4 p i R P N + 6 E B q E K i G l n C h p f 0 r F R d c c 4 G 2 x b y E r 0 v p / + S 4 X q 0 1 q + 6 B W 9 r e G d U x Q 9 b I O i m T G t k k 2 2 S P 7 J M 2 E e S G 3 J E H 8 u j c O v f O k / P 8 G R 1 z R j O r 5 A e c l 3 f p r 5 0 D < / l a t e x i t > e R(x pa(3) 2 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " 0 2 f F H c L e t Q s R W f L r w B j A e q T 5 d K 8 = " > A A A C H H i c b V A 9 b 9 s w E K W S t H X d j z j t 2 E W I U c B e D M k x 0 o 5 B u m R 0 g T o 2 Y K s C R Z 1 s w h Q p k K e k B q E f k i V / J U u G F k W X D g X 6 b 0 I 7 H h I 7 D z j g 8 b 0 7 8 O 4 l h e A G g + C / t 7 O 7 9 + z 5 i 9 r L + q v X b 9 7 u N w 7 e n R t V a g Y D p o T S o 4 Q a E F z C A D k K G B U a a J 4 I G C b z L 0 t / e A H a c C W / 4 a K A K K d T y T P O K D o p b h x N S p k 6 H 9 B O h J J T A R l S r d V l Z W W c f L e t X r t q W f u j i r v u 0 W 1 X 7 a q K G 8 2 g E 6 z g b 5 N w T Z p k j X 7 c + D t J F S t z k M g E N W Y c B g V G l m r k T E B V n 5 Q G C s r m d A p j R y X N w U R 2 d V z l f 3 R K 6 m d K u 5 L o r 9 S H E 5 b m x i z y x H X m F G d m 0 1 u K T 3 n j E r P P k e W y K B E k u / 8 o K 4 W P y l 8 m 5 a d c A 0 O x c I Q y z d 2 u P p t R T R m 6 v O o u h H D z 5 G 1 y 3 u 2 E x 5 3 e 1 1 7 z 5 H Q d R 4 1 8 I I e k R U L y i Z y Q M 9 I n A 8 L I F b k h P 8 k v 7 9 q 7 9 X 5 7 f + 5 b d 7 z 1 z H v y C N 6 / O + z m o n c = < / l a t e x i t > n (4 ) b ( x (2 ) 2 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " 7 V B 0 I G V X k N V o H 4 C 4 6 h S b Q E x v k I Q = " > A A A C E X i c b V C 7 T s M w F H V 4 l v I q M L J E V E h h q R J U A W M F C 2 O R 6 E N q S + U 4 T m r V s S P 7 B l R F + Q U W f o W F A Y R Y 2 d j 4 G 9 z H A C 1 H u l dl N E M 9 X 7 p q x t I k s Z U A O F Y 6 4 7 n J t D L s A J G O M 2 L 3 V T T B J M h j m j H U I F j q n v Z 5 K L c P j Z K Y I d S m R J g T 9 T f G x m O t R 7 F v p m M M Q z 0 v D c W / / M 6 K Y Q X v Y y J J A U q y P S h M O U 2 S H s c j x 0 w R Q n w k S G Y K G b + a p M B V p i A C a l o Q v D m T 1 4 k z d O K d 1 a p 3 l T L t c t Z H A V 0 i I 6 Q g z x 0 j m r o G t V R A x H 0 i J 7 R K 3 q z n q w X 6 9 3 6 m I 4 u W b O d A / Q H 1 u c P M c + d 1 w = = < / l a t e x i t > n (1 ) (a 1 ) ! < l a t e x i t s h a 1 _ b a s e 6 4 = " / / v y U p X N 0 q X + b S O D i j Z X A j q P C k I = " > A A A C E H i c b V A 9 S w N B E N 2 L X z F + R S 1 t D o M Y m 3 A X R C 1 F G 8 s I J g p J D H u b u b h k b / f Y n V P C c T / B x r 9 i Y 6 G I r a W d / 8 Z N c o V f D w Y e 7 8 0 w M y + I B T f o e Z 9 O Y W Z 2 b n 6 h u F h a W l 5 Z X S u v b 7 S M S j S D J l N C 6 a u A G h B c Q h M 5 C r i K N d A o E H A Z D E / H / u U t a M O V v M B R D N 2 I D i Q P O a N o p V 5 5 t 5 P I v v U B 0 4 5 Q c i A g R K q 1 u s v S 6 D q t + n t Z l f b q e 1 m v X P F q 3 g T u X + L n p E J y N H r l j 0 5 f s S Q C i U x Q Y 9 q + F 2 M 3 p R o 5 E 5 C V O o m B m L I h H U D b U k k j M N 1 0 8 l D m 7 l i l 7 4 Z K 2 5 L o T t T v E y m N j B l F g e 2 M K N 6 Y 3 9 5 Y / M 9 r J x g e d V M u 4 w R B s u m i M B E u K n e c j t v n G h i K k S W U a W 5 v d d k N 1 Z S h z a h k Q / B / v / y X t O o 1 / 6 C 2 f 7 5 f O T 7 J 4 y i S L b J N q s Q n h + S Y n J E G a R J G 7 s k j e S Y v z o P z 5 L w 6 b 9 P W g p P P b J I f c N 6 / A E 0 N n V o = < / l a t e x i t > m (1 ) (a 2 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " o 5 W h I V 1 p 3 / C I n v h C q t a t G l P y K g k = " > A A A C D 3 i c b V A 9 S w N B E N 3 z 2 / g V t b Q 5 D E r S h L s Q 1 D J o Y 6 l g T C C J Y W 8 z l y z u 7 R 6 7 c 0 o 4 7 h / Y + F d s L B S x t b X z 3 7 i J K T T x w c D j v R l m 5 g W x 4 A Y 9 7 8 u Z m 1 9 Y X F p e W c 2 t r W 9 s b u W 3 d 6 6 N S j S D O l N C 6 W Z A D Q g u o Y 4 c B T R j D T Q K B D S C 2 7 O R 3 7 g D b b i S V z i M o R P R v u Q h Z x S t 1 M 0 f t t X I B k z b Q s m + g B C p 1 u o + S 6 O b t F g p Z U X a 9 U t Z N 1 / w y t 4 Y 7 i z x J 6 R A J r j o 5 j / b P c W S C C Q y Q Y 1 p + V 6 M n Z R q 5 E x A l m s n B m L K b m k f W p Z K G o H p p O N / M v f A K j 0 3 V N q W R H e s / p 5 I a W T M M A p s Z 0 R x Y K a 9 k f i f 1 0 o w P O m k X M Y J g m Q / i 8 J E u K j c U T h u j 2 t g K I a W U K a 5 v d V l A 6 o p Q 5 t R z o b g T 7 8 8 S 6 4 r Z f + o X L 2 s F m q n k z h W y B 7 Z J 0 X i k 2 N S I + f k g t Q J I w / k i b y Q V + f R e X b e n P e f 1 j l n M r N L / s D 5 + A a E h J z u < / l a t e x i t > m (2) (a1 ) < l a t e x i t s h a 1 _ b a s e 6 4 = " q l k 2 7 4 s 7 d R w z y 1 K F k j z A C t d w a f w = " > A A A C E X i c b V D L S s N A F J 3 4 r P U V d e k m W I R 2 U 5 J S 1 G X R j c s K 9 g F t D J P p t B 0 6 m Q k z N 0 o J + Q U 3 / o o b F 4 q 4 d e f O v 3 H 6 W G j r g Q u H c + 7 l 3 n v C m D M N r v t t r a y u r W 9 s 5 r b y 2 z u 7 e / v 2 w W F T y 0 Q R 2 i C S S 9 U O s a a c C d o A B p y 2 Y 0 V x F H L a C k d X E 7 9 1 T 5 V m U t z C O K Z + h A e C 9 R n B Y K T A L n Y T 0 T M + h b T L p R g o N h g C V k o + Z K m 4 S 4 u V U l b E g V f K A r v g l t 0 p n G X i z U k B z V E P 7 K 9 u T 5 I k o g I I x 1 p 3 P D c G P 8 U K G O E 0 y 3 c T T W N M R n h A O 4 Y K H F H t p 9 O P M u f U K D 2 n L 5 U p A c 5 U / T 2 R 4 k j r c R S a z g j D U C 9 6 E / E / r 5 N A / 8 J P m Y g T o I L M F v U T 7 o B 0 J v E 4 P a Y o A T 4 2 B B P F z K 0 O G W K F C Z i Q 8 i Y E b / H l Z d K s l L 2 z c v W m W q h d z u P I o W N 0 g o r I Q + e o h q 5 R H T U Q Q Y / o G b 2 i N + v J e r H e r Y 9 Z 6 4 o 1 n z l C f 2 B 9 / g A z W 5 3 Y < / l a t e x i t > n (2) (a1 ) ! < l a t e x i t s h a 1 _ b a s e 6 4 = " U u D A Q u f u C g X 7 / 0 H S t l m y c 4 F a e w c = " > A A A C E X i c b V C 7 T s M w F H X K q 5 R X g J E l o k I K S 5 V U F T B W s D A W i T 6 k t l S O 4 7 Z W H T u y b 0 B V 1 F 9 g 4 V d Y G E C I l Y 2 N v 8 F t M 0 D L k e 7 V 0 T n 3 y r 4 n i D n T 4 H n f V m 5 l d W 1 9 I 7 9 Z 2 N r e 2 d 2 z 9 w 8 a W i a K 0 D q R X K p W g D X l T N A 6 M O C 0 F S u K o 4 D T Z j C 6 m v r N e 6 o 0 k + I W x j H t R n g g W J 8 R D E b q 2 W 4 n E a H x K a Q d L s V A s c E Q s F L y Y Z K K u 9 Q t n 0 5 c 3 D O 9 Z x e 9 k j e D s 0 z 8 j B R R h l r P / u q E k i Q R F U A 4 1 r r t e z F 0 U 6 y A E U 4 n h U 6 i a Y z J C A 9 o 2 1 C B I 6 q 7 6 e y i i X N i l N D p S 2 V K g D N T f 2 + k O N J 6 H A V m M s I w 1 I v e V P z P a y f Q v + i m T M Q J U E H m D / U T 7 o B 0 p v E 4 I V O U A B 8 b g o l i 5 q 8 O G W K F C Z i Q C i Y E f / H k Z d I o l / y z U u W m U q x e Z n H k 0 R E 6 R i 7 y 0 T m q o m t U Q 3 V E 0 C N 6 R q / o z X q y X q x 3 6 2 M + m r O y n U P 0 B 9 b n D z T h n d k = < / l a t e x i t > n (2) (a2 ) ! < l a t e x i t s h a 1 _ b a s e 6 4 = " G 1 b x P B q u y D P b y X u Z V J m x X x b h b d I = " > A A A C D 3 i c b V C 7 T g M x E P T x D O E V o K Q 5 E Y F C E 9 1 F C C g R N J R B I g 8 p C Z H P 2 Q s W P v t k 7 4 G i 0 / 0 B D b 9 C Q w F C t L R 0 / A 2 + J A W v k X Y 1 m t m V v R P E g h v 0 v E 9 n Z n Z u f m G x s F R c X l l d W y 9 t b D a N S j S D B l N C 6 X Z A D Q g u o Y E c B b R j D T Q K B L S C m 7 P c b 9 2 C N l z J S x z F 0 I v o U P K Q M 4 p W 6 p f 2 u i q 3 A d O u U H I o I E S q t b r L 0 u g q r d T 2 s w r t 2 9 4 v l b 2 q N 4 b 7 l / h T U i Z T 1 P u l j + 5 A s S Q C i U x Q Y z q + F 2 M v p R o 5 E 5 A V u 4 m B m L I b O o S O p Z J G Y H r p + J 7 M 3 b X K w A 2 V t i X R H a v f N 1 I a G T O K A j s Z U b w 2 v 7 1 c / M / r J B g e 9 1 I u 4 w R B s s l D Y S J c V G 4 e j j v g G h i K k S W U a W 7 / 6 r J r q i l D m 1 H R h u D / P v k v a d a q / m H 1 4 O K g f H I 6 j a N A t s k O q R C f H J E T c k 7 q p E E Y u S e P 5 J m 8 O A / O k / P q v E 1 G Z 5 z p z h b 5 A e f 9 C 4 Y K n O 8 = < / l a t e x i t > m (2) (a2 )The entropy terms for inference types other than the "planning inference" were introduced in prior work and are compiled here for convenience.First we will derive a general variational expression that depends on an inverse temperature β. The function f (x, a) will be an (unnormalized) factor graph, with the structure of Fig. 1[Left] .EQUATIONMarginal inference This is the standard VI problem, see e.g., (Jordan et al., 1999) , and can be recovered from Eq. ( 11) by setting β = 1. Then we get logx,a f (x, a) = max q(x,a)⟨log f (x, a)⟩ q(x,a) + H q (x, a).Since f (x, a) forms a chain in our application of interest (see Fig. 1 [Left]), we know that the optimal posterior will as well. We can thus decompose H q (x, a) using the chain rule to obtain the expression from Table 1 , H marginal (q) = H q (x 1 ) +T -1 t=1 H q (x t+1 , a t |x t ).Maximum-a-posterior (MAP) inference MAP inference can be recovered from Eq. ( 11) by settingβ → ∞ max x,a log f (x, a) = lim β→∞ 1 β log x,a f (x, a) β = max q(x,a)⟨log f (x, a)⟩ q(x,a) + lim β→∞ 1 β H q (x, a), (13) where lim β→∞ 1 β H q (x, a) produces the term H marginal (q) = 0 from Table 1 . The maximization is an LP problem, see (Weiss et al., 2012) . This problem can be relaxed into a local polytope, giving rise to most well-known methods for approximate MAP inference, such as dual decomposition. See e.g., (Sontag et al., 2011) . An optimal distribution solving this problem is a Dirac delta centered at one of the MAP solutions of the problem.Marginal maximum-a-posterior (MMAP) inference MMAP combines the previous two types of inference, see (Liu and Ihler, 2013) for detailed (approximate) solution methods. We can reuse the previous results to obtain the variational expressionmax a log x f (x, a) Eq. (12) = max a max q(x|a) ⟨log f (x, a)⟩ q(x|a) + H(q(x|a)) Eq. (13) = max q(x,a) ⟨log f (x, a)⟩ q(x,a) + H q (x, a) -H q (a) = max q(x,a) ⟨log f (x, a)⟩ q(x,a) + H q (x, a) - T -1 t=1 H q (a t )To understand the last equality, first note that T -1 t=1 H q (a t ) ≥ H q (a), since the latter is the joint entropy. This means that the last expression is necessarily lower than or equal to the previous one. It is not yet clear why equality is always achievable. To see this note that, analogously to the previous section, the optimal q(a) will be a Dirac delta centered at an optimal sequence a. That means that the optimal variational distribution of MMAP factorizes as q(x, a) = q(x)T -1 t=1 q(a t ). This in turn means that, for the optimal distribution T -1 t=1 H q (a t ) = H q (a). So the last expression can always match the previous one, and given that is also a lower bound, it must have the same optimal distribution and value.Just like we did for marginal inference, we can now decompose H q (x, a) using the chain rule to obtain the expression from Table 1 , H MMAP (q) = H q (x 1 ) + T -1 t=1 H q (x t+1 , a t |x t ) -H q (a t ).We want to prove that for an arbitrary variational distribution qF MAP λ (q) F marginal U λ (q) ≤ F MMAP λ (q) ≤ F planning λ (q) ≤ F marginal λ (q)and that, when we assume that dynamics are deterministic (which we also take to imply that the first state follows a deterministic distribution, i.e., it is known), the optimal values of the above bounds wrt q satisfy the following relationshipsF marginal U λ ≤ F MAP λ = F MMAP λ = F planning λ ≤ F marginal λ .Since the energy terms are identical for all these bounds, we will simply have to prove the relationship between the corresponding entropies, as given in Table 1 .Proof that F planning λ (q) ≤ F marginal λ (q)The marginal entropy termH marginal (q) = H q (x 1 ) + T -1 t=1 H q (x t+1 , a t |x t )clearly upper bounds the "planning inference" entropy termH planning (q) = H q (x 1 ) + T -1 t=1 H q (x t+1 |a t , x t )since H q (x t+1 , a t |x t ) = H q (x t+1 |a t , x t ) + H q (a t |x t ), and entropies are non-negative.Proof that F MMAP λ (q) ≤ F planning λ (q) (and F MMAP λ = F planning λ for deterministic dynamics)The "planning inference" entropy termH planning (q) = H q (x 1 ) + T -1 t=1 H q (x t+1 |a t , x t )clearly upper bounds the MMAP entropy termH MMAP (q) = H q (x 1 ) + T -1 t=1 H q (x t+1 , a t |x t ) -H q (a t ) = H q (x 1 ) + T -1 t=1 H q (x t+1 |x t , a t ) + (H q (a t |x t ) -H q (a t )) = H q (x 1 ) + T -1 t=1 H q (x t+1 |x t , a t ) -I q (x t ; a t )since the mutual information I q (x t ; a t ) is non-negative.In exact MMAP variational inference (Liu and Ihler, 2013) , at the optimal solution, the variational distribution factorizes as q(x, a) = q(x)T -1 t=1 q(a t ), as we mentioned in Appendix E. This is because MMAP finds a single, deterministic, optimal sequence of actions. Therefore I q (x t ; a t ) = 0 when evaluated at the q that maximizes F MMAP λ (q). Setting that term to zero in the MMAP entropy results in the same expression as the "planning inference" entropy. However, in "planning inference", the optimal variational distribution does not need to factorize in the way it does for MMAP, so a richer variational distribution is possible, and F planning λ can be strictly larger than F MMAP λ for some problems.However, when dynamics are deterministic and the first state x 1 is known, the optimal plan is a deterministic sequence of states and actions, and the optimal "planning" variational distribution is a Dirac delta at those states and actions. Therefore, the optimal distribution for planning also factorizes as q(x, a) = q(x)T -1 t=1 q(a t ) when the dynamics are deterministic. Therefore, in that case the optimal values coincide F planning λ = F MMAP λ (and so do the optimal variational distributions).We can also show that at the optimal q value the entropies of both bounds are zero. P (x t+1 |a t , x t ) (and P (x 1 )) are deterministic, q(x t+1 |a t , x t ) = P (x t+1 |a t , x t ) (and q(x 1 ) = P (x 1 )) for both of these bounds to be larger than -∞ (see Section 4.2). Since these are deterministic distributions, H q (x t+1 |a t , x t ) = 0 and H q (x 1 ) = 0, which in turn makes H planning (q) = 0 at the optimal q. I.e., H planning = 0. Since I q (x t ; a t ) = 0, also H MMAP = 0.Proof that F MAP λ (q) ≤ F MMAP λ (and F MAP λ = F MMAP λ (q) for deterministic dynamics)The MMAP entropy can be rearranged in the following formH MMAP (q) = H q (x 1 ) + T -1 t=1 H q (x t+1 , a t |x t ) -H q (a t ) = H q (x 1 , a 1 , . . . , x T -1 , a T -1 , x T ) - T -1 t=1 H q (a t ) = I q (x 1 ; a 1 ; . . . , x T -1 ; a T -1 ; x T ) + T t=1 H q (x t ) ≥ 0,where the last equality follows because the mutual information and entropy are non-negative. This clearly upper bounds the MAP entropy term H MAP (q) = 0.When dynamics are deterministic and the first state x 1 is known, we can reuse the results of the previous proof. We know that in that case, the optimal variational distribution for MMAP and planning is a Dirac delta at the optimal sequence of states and actions, and that the bound only contains the energy terms (since the entropy terms for any Dirac delta distribution will be zero). The problem of finding such distribution is exactly the MAP energy minimization problem. Thus, if dynamics are deterministic the optimal values coincide F MMAP λ = F MAP λ (and so do the optimal variational distributions).Proof that F marginal U λ (q) ≤ F MMAP λ (q)The MMAP entropy termH MMAP (q) = H q (x 1 ) + T -1 t=1 (H q (x t+1 , a t |x t ) -H q (a t ))clearly upper bounds H Marginal U (q), i.e.,H Marginal U (q) = H q (x 1 ) + T -1 t=1 (H q (x t+1 , a t |x t ) -log N a )since H q (a t ) ≤ log N a , with equality being attained when q(a t ) is uniform.Proof that F marginal U λ ≤ F MAP λ for deterministic dynamicsWe can rewrite the entropy corresponding to the marginal bound with uniform prior asH Marginal U (q) = H q (x 1 ) + T -1 t=1 (H q (x t+1 , a t |x t ) -log N a ) = H q (x 1 ) + T -1 t=1 (H q (x t+1 |a t , x t ) + H q (a t |x t ) -log N a ).When dynamics are deterministic and the first state x 1 is known, we know from the previous proofs that at the optimal value q of F marginal U λ (q) we have H q (x 1 ) = 0 and H q (x t+1 |a t , x t ) = 0. The remaining terms, of the form H q (a t |x t )log N a are trivially non-positive (the conditional entropy over the actions cannot be larger than the log of the cardinality of the action space). This means that at the maximum value of F marginal U λ (q) wrt q we have H Marginal U (q) ≤ 0. Since H MAP (q) = 0, we know that with deterministic dynamicsF marginal U λ ≤ F MAP λ .In the planning literature, many algorithms make the assumption of a deterministic environment (Geffner and Bonet, 2022; Hoffmann and Nebel, 2001; Helmert, 2006; etc) . In order to extend these algorithms to the case of stochastic dynamics, the idea of determinization in hindsight has been developed (Yoon et al., 2008) . It starts by factoring out all the stochasticity from the transition probability into the random variables γ= {γ t } t=T -1 t=1 P (x t+1 |x t , a t ) = γt P det (x t+1 |x t , a t , γ t )P (γ t ) = ⟨P det (x t+1 |x t , a t , γ t )⟩ P (γt) .This factorization is always possible, and γ is known as the collection of exogenous variables in structural equation modeling (Pearl, 2012; Bareinboim and Pearl, 2016; Rubenstein et al., 2017) . We will define P det (x|a, γ) ≡ P det (x 1 |γ 0 )T -1 t=1 P det (x t+1 |x t , a t , γ t ). Then we can use it to obtain an upper bound on the exact utilityF planning λ=1 = log max π ⟨⟨exp(R(x, a))⟩ Pdet(x|a,γ)π(a|x) ⟩ P (γ) ≤ log⟨max π ⟨exp(R(x, a))⟩ Pdet(x|a,γ)π(a|x) ⟩ P (γ) = F det. planning λ=1that has a natural interpretation: the dynamics of a stochastic environment depends on random variables γ that get drawn at each time step, if we knew their value ahead of time, we could treat the environment as deterministic, find an optimal plan and estimate its utility. Because we have hindsight, i.e., the deterministic planner can see the value of future γ t ahead of time, it can make better choices than if these were revealed online, so the utility estimation, if exact, upper bounds the original quantity. See (Yoon et al., 2008) for more details.The above process uses a sample average: it alternates between sampling γ ∼ P (γ) and running a deterministic planner. Using the variational framework for planning it is possible to find a closed form expression for F det. planning λ=1 .First, let us expand the determinization boundF det. planning λ=1 Eq. (9) = max q(γ) ⟨log max π ⟨exp(R(x, a))⟩ Pdet(x|a,γ)π(a|x) + log P (γ)⟩ q(γ) + H q (γ) = max q(γ) ⟨F planning λ=1,γ ⟩ q(γ) + ⟨log P (γ)⟩ q(γ) + H q (γ)in terms of our exact planning utility for a given future γ, F planning λ=1,γ . This quantity and the corresponding bound are defined as the usual ones, but conditioned on γF planning λ=1,γ = max q F planning λ=1 (q|γ); F planning λ=1 (q|γ) = -E λ=1 (q|γ) + H planning (q|γ).To be precise, the corresponding energy E λ=1 (q|γ) and entropy H planning (q|γ) terms areEQUATIONEQUATIONSince the conditional dynamics are now deterministic, log P det (x t+1 |x t , a t , γ t ) can only take the values 0 and -∞. When maximizing over q, it is obvious we must choose q(x t+1 |x t , a t , γ t ) = P det (x t+1 |x t , a t , γ t ) ∀ t and q(x 1 |γ 0 ) = P det (x 1 |γ 0 ), to avoid putting any mass on the -∞ value of the previous term, which would result in the whole score function becoming -∞. For such choice, H det. planning (q|γ) = 0 and the mentioned energy term also cancels, leavingEQUATIONTherefore, determinization for multiplicative exponentiated rewards can be exactly expressed as a concave variational bound of the formF det. planning λ=1 = max qγ ⟨F planning λ=1 (q|γ)⟩ q(γ) + T -1 t=0 ⟨log P (γ t )⟩ q(γt) + H q (γ t ) (17) s.t. a1,γ1 q(x 1 , a 1 , γ 1 ) = γ0 P det (x 1 |γ 0 )q(γ 0 ) at+1,γt+1 q(x t+1 , a t+1 , γ t+1 ) = xt,at,γt P det (x t+1 |x t , a t , γ t )q(x t , a t , γ t ) ∀ t ;q(x t , γ t ) = at q(x t , a t , γ t ) ∀ t ; q(x t , a t , γ t ) ≥ 0 ∀t, where we have defined q γ ≡ {q(x t , a t , γ t )} T -1 t=1 ∪ q(γ 0 )In the case of a standard MDP, it is trivial to see that determinization, which provides an upper bound on the exact utility, cannot improve on our VI bound F planning λ=1 , since the latter is exact. In this section we will show that this is also the case for factored MDPs in which the deterministic MAP problem is solved using an LP MAP relaxation.First, we will show that F planning λ=1 can be rewritten in a more convenient way to compare with determinization, in the standard, non-factored case. We expandF planning λ=1 = max q F planning λ=1 (q) = max q -E λ=1 (q) + H planning (q)and substitute log P (x t+1 |x t , a t ) = max q(γt|xt+1,xt,at)⟨log P det (x t+1 |x t , a t , γ t )⟩ q(γt|xt+1,xt,at) - T t=1 KL(q(γ t |x t+1 , x t , a t )||P (γ t )) inside E λ=1 (q) to get F planning λ=1 = max q ⟨F planning λ=1 (q|γ)⟩ q(γ) + T -1 t=0 ⟨log P (γ t )⟩ q(γt) + H q (x t+1 , γ t |a t , x t )where q(x t+1 |x t , a t , γ t ) = P det (x t+1 |x t , a t , γ t ) ∀ t for the same reasons as above. To compact notation, we use the convention that H q (x 1 , γ 0 |x 0 , a 0 ) = H q (x 1 , γ 0 ) (since x 0 , a 0 are not defined), and similarly H q (γ 0 |x 0 , a 0 ) = H q (γ 0 ). Noting that H q (x t+1 , γ t |a t , x t ) = H q (x t+1 |x t , a t , γ t ) + H q (γ t |a t , x t ) and that H q (x t+1 |x t , a t , γ t ) = 0 because q(x t+1 |x t , a t , γ t ) is deterministic, we getEQUATIONs.t.a1,γ1q(x 1 , a 1 , γ 1 ) = γ0 P det (x 1 |γ 0 )q(γ 0 ) at+1,γt+1q(x t+1 , a t+1 , γ t+1 ) = xt,at,γt P det (x t+1 |x t , a t , γ t )q(x t , a t , γ t ) ∀ t ;q(x t , γ t ) = at q(x t , a t , γ t ) ∀x t , γ t , t; q(x t , a t , γ t ) ≥ 0 ∀t.Compare Eqs. ( 17) and ( 18). Although we already knew this, with this particular formulation it is very easy to see that F planning λ=1 ≤ F det. planning λ=1 , since they are identical except for the terms H q (γ t |a t , x t ) ≤ H q (γ t ) ∀t. This holds for the same q, but also establishes a relationship between both upper bounds at their maximum wrt q.With this result, we can return to the factored MDP case. As in the main text, here we will consider R to be only a function of x t . We can take Eqs. ( 17) and ( 18) and relax q γ from the marginal polytope M to the local polytope L, using the pseudo-marginals qγ ≡ {q(xpa(i) t , a t , γ (i) t )} t=T -1,i=Ne t=1,i=1 ∪ {q(γ (i) 0 )} Ne i=1 ∪ {q(x pa(i) t)} t=T,i=Ne+Nr t=1,i=Ne+1 . For Eq. ( 17), and substituting the value from Eq. ( 16), this produces a factored MDP upper bound corresponding to determinization with λ = 1F det. planning λ=1 = max qγ T t=1 Ne+Nr i=Ne+1 ⟨R(x pa(i) t )⟩ q(x pa(i) t ) + Ne i=1 ⟨log P (γ (i) t-1 )⟩ q(γ (i) t-1 ) + H q (γ (i) t-1 ) s.t. a1,γ (i) 1 q(x (i) 1 , a 1 , γ (i) 1 ) = γ (i) 0 P det (x (i) 1 |γ (i) 0 )q(γ (i) 0 ) ∀x 1 , i at+1,γ (i) t+1 q(x (i) t+1 , a t+1 , γ (i) t+1 ) = x pa(i) t ,at,γ (i) t P det (x (i) t+1 |x pa(i) t , a t , γ (i) t )q(x pa(i) t , a t , γ (i) t ) ∀x (i) t+1 , t, i ∈ 1, . . . , N eand pseudo-marginal constraints, which can be interpreted as an outer maximization over q(γ) and an inner MAP optimization of the (conditional on γ) deterministic dynamics problem, solved with an LP relaxation (Sontag et al., 2011) . For Eq. ( 18), and also substituting the value from Eq. ( 16), this results in a different formulation of the problem Eq. ( 7)F planning λ=1 = max qγ T t=1 Ne+Nr i=Ne+1 ⟨R(x pa(i) t )⟩ q(x pa(i) t ) + Ne i=1 ⟨log P (γ (i) t-1 )⟩ q(γ (i) t-1 ) + H q (γ (i) t-1 |x t-1 , a t-1 ) s.t. a1,γ (i) 1 q(x (i) 1 , a 1 , γ (i) 1 ) = γ (i) 0 P det (x (i) 1 |γ (i) 0 )q(γ (i) 0 ) ∀x 1 , i at+1,γ (i) t+1 q(x (i) t+1 , a t+1 , γ (i) t+1 ) = x pa(i) t ,at,γ (i) t P det (x (i) t+1 |x pa(i) t , a t , γ (i) t )q(x pa(i) t , a t , γ (i) t ) ∀x (i) t+1 , t, i ∈ 1, . . . , N eand pseudo-marginal constraints,In the same way as for the non-factorized MDP, it is easy to see that F planning λ=1 ≤ F det. planning , while both upper bound the exact F planning λ=1 . This means that in the case of (exponentiated) multiplicative rewards (λ = 1) our proposed bound should be no worse than determinization. Also, F det. planning λ=1 allows us to compute the determinization bound as a single, solvable, concave optimization, rather than having to resort to sampling and solving a theoretically infinite number of deterministic problems (this holds when each problem would be solved using an LP relaxation of the MAP problem).The synthetic MDPs use binary state and actionss, T = 4 time steps and follow the connectivity scheme of Fig. 1 [Right]. The stochasticity level of the MDPs is controlled by generating their dynamics according to P (x t+1 |x t , a t ) = P s xt+1,xt,at /Z xt,at where Pxt+1,xt,at ∼ U [0, 1] and choosing the exponent s and the divisor Z xt,at to obtain normalized distributions of the desired total normalized entropy H MDP . Each entity has two parent entities and we provide a single reward of 1 for reaching the state 0 of entity 1 at the last step T . Having a single reward allows comparing methods with arbitrary λ and create a pure planning problem (see Section 4.2).As discussed in Section 4.2, a common flaw among all inference types (other than planning inference) is that they cannot anticipate reacting to the environment. Even the tightest one, MMAP, makes plans assuming that it will only be able to take a predefined sequence of actions. This can severely underestimate the value of an action if, to extract future reward, reacting to the environment state is necessary. In other words, MMAP is optimal only when the best policy π t (a t |x t ) ignores the state and can be represented as π t (a t ). MAP inference shares that limitation, and additionally lacks path integration. I.e., MAP inference makes decisions based on the score of a single action-state trajectory, rather than a combination of these.In order to analyze the behavior of different inference types of inference with reactivity, we create an MDP with two entities, each with categorical states 0, . . . , 5. We use a horizon of T = 7 time steps, placing reward only on the last time step. There are a total of 8 actions.The first entity describes the location of the agent, and has a special goal state "0" that needs to be reached at the last time step. The second entity describes the dynamics of the first entity and the reward achieved at the goal. Actions 0, . . . , 5 allow the agent to move to any location in a single step. Actions 6, 7 allow the agent to modify the dynamics of the first entity, respectively decreasing or increasing the needed level of reactivity of a planner. Skill teaching, Sysadmin, and Traffic) used in the ICAPS 2011 International Probabilistic Planning Competition (Sanner, 2011) . Figure 3 shows the average cumulative reward of all domains. Table 2 shows the corresponding objective and reference for each approach. There are 10 instances for each domain. All instances have a horizon of 40 and a discount factor of 1. The cumulative reward is averaged over 30 simulations for each instance and the plotted error bar shows its standard error of the mean. Given the current state x t , the transition probability P (x t+1 |a t , x t ), and the reward function R, each approach infers the best next action a t at each time step. The reward function for all 6 domains only depend on the state x. The cumulative reward is the sum of the rewards of the initial state and the following 39 states. For all inference approaches, we run with a look ahead horizon of both 4 and 9. We follow the settings in (Wu and Khardon, 2022) where the look ahead horizon is truncated if it extends beyond the remaining time steps. The horizon with the higher average cumulative reward is then selected for each instance. The experiment evaluates over two look ahead horizons due to the observation that for some domain instances a longer horizon may lead to worse estimates. For each simulated run, the same set of random numbers are applied to the simulated environment to reduce noise when comparing different inference approaches. All experiments were ran on CPU machines in the cloud. The backward mean field variational inference approach (MFVI-Bwd) is based on the implementation in (Wu and Khardon, 2022 -url: https://github.com/Zhennan-Wu/AISPFS), in which the mean field approximation q ϕ is the product of independent factors. q ϕ is first obtained by maximizing the ELBO of the true posterior under the condition that the maximum accumulated reward is reached using the EM algorithm. The action is then selected based on the marginal q ϕ (a). In the experiment, the maximum number of iterations is set to 100 and the convergence threshold is set to 0.1 for the EM algorithm. MFVI-Bwd experiments were ran on a single CPU machine with 32 virtual cores. All 30 simulations were ran in parallel for each task instance.The backward collapsed variational inference approach (CSVI-Bwd) is proposed in (Wu and Khardon, 2022) . It uses collapsed variational inference to effectively marginalizes out variables other than the actions to achieve a tighter ELBO. The authors have shown that this approach out performs MFVI-Bwd. CSVI-Bwd experiments were ran with the same hardware setup as MFVI-Bwd.The Algebraic Rollout Algorithm (ARollout) introduced in Cui et al., 2015 is equivalent to belief propagation when conditioned on actions as shown in Cui et al., 2018. In our experimental setting which the search depth is fixed with no computation time limit, ARollout is equivalent to the original SOGBOFA (symbolic online gradient based optimization for factored actions) approach introduced in (Cui and Khardon, 2016) . While ARollout performs approximate aggregate rollout simulations to evaluate each action, SOGBOFA uses the gradient of the accumulated reward to update actions for exploration and can be advantageous when the action space is large given a computation time constraint. In this experiment, we use the results of forward belief propagation to represent ARollout.For each time step, the action with the highest estimated accumulated reward is selected. The estimated accumulated reward is calculated by running a forward pass on the factored MDP representing the problem conditioned on the next action. ARollout experiments were ran on CPU machines with 2 virtual cores. All simulations were ran in parallel.SOGBOFA-LC is based on the Lifted Conformant SOGBOFA implemented in (Cui et al., 2019 -url: https://github.com/hcui01/SOGBOFA). SOGBOFA-LC has two differences over the original SOGBOFA. First, it uses a lifted graph that saves computation by identifying same operations. This improvement in computation speed doesn't have an effect in our experiment result since we provide enough computation time for the given maximum search depth. Second, it uses conformant solutions, which the evaluation of the next action is based on a linear rollout plan that best supports the action. This is achieved by calculating the gradient with respect to all actions within the search depth.In our experiment, the search depth is set to 9 or 4 based on the look ahead horizon. The number of gradient updates is set to 500 following the experimental setting in Wu and Khardon, 2022. The allowed time is set to 50000 per iteration, which is sufficient for 500 updates given the assigned depth. SOGBOFA-LC experiments were ran on CPU machines with 4 virtual cores sequentially.Note that the RDDL files in the repository (https://github.com/hcui01/SOGBOFA or https:// github.com/Zhennan-Wu/AISPFS/tree/master/SOGBOFA) have different initial states from the original competition for some instances in the elevator and skill teaching domains. These differences were corrected to match the original competition settings in our experiments. Modifications were also made to use the same random numbers in the environment as other experiments and to measure the standard error of the mean instead of the standard deviation.The Variational Inference Linear Programming (VI LP) approach uses the GLOP solver in Google's OR-Tools (Perron and Furnon, 2024) to solve the linear programming (LP) problem derived from each task instance with the target of maximizing the expected accumulated reward. Constraints on states that are specified in the original RDDL problem is added to the LP problem. Among the six domains only the elevator and crossing traffic domains have such constraints. These constraints specifies that the elevator/robot can't be at different floors/locations at the same time step.The solver is ran for each next action at each time step. The next action that has the highest estimated expected accumulated reward based on the solver is selected. See Section 3.1 for more details of this approach. VI LP experiments were ran on CPU machines with 16 virtual cores. All simulations were ran in parallel. For each iteration, LP solvers for each next action were ran concurrently with multiprocessing.Note that setting a value for λ is meaningless if the reward can have arbitrary scaling (and for the case of IPPC in which rewards are additive, the scaling is indeed arbitrary). Therefore, we first normalize all rewards to have a maximum point-to-point variation of 1.0. λ is chosen as a reward multiplier on top of that normalization. The closer to 0 that we set λ then, the closer we are to the additive limit.Although outside the scope of this work, it is actually possible to set λ to exactly zero in VBP (the problem remains non-convex, but the message updates within each time step become an LP problem). However, at least in a straighforward implementation, we observed such message updates to not result in a good optimization of our score function, and often not converging. We attribute this to the degeneracy of the solutions in the limit. Using instead a small value of λ = 0.3 had a favorable effect on convergence, while remaining close enough to the additive limit. Empirically, we found that most problems were not very sensitive to the choice of λ.For each time step, VBP messages are propagated concurrently for a maximum of 150K iterations with 0.1 damping. The ϵ value is annealed every 300 iterations from a value of 1 to 0.01 based on the formula described in Appendix D. The next action with the highest expected accumulated reward is then selected. See Section 3.1 and Appendix D for more details of this approach. VBP experiments were ran on CPU machines with 2 virtual cores. All simulations were ran in parallel.• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [No] Justification: We provided detail information of the type of compute worker used for the experiment but did not record the time of execution. The main contribution of this work is to provide a theoretical framework for comparing different planning algorithm.The different approaches ran in the experiment uses different hardware and programming language, therefore the measured time of computation may not be directly comparable. Our experimental setting on the IPPC 2011 competition is based on experiments in (Wu and Khardon, 2022) , which there are no limit to the run time and the goal is to understand the quality of decisions.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: Our experiments do not include human subjects and all experiment are based on simulated environments. Our main contribution is providing a theoretical framework for analyzing different planning approaches and we do not expect to have immediate social impacts.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [No] Justification: Our main contribution in this paper is providing a theoretical framework for analyzing different planning approaches. We do not expect social impacts at this stage of development.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: No trained model or dataset for training is used in this work.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: All approaches used for comparison in experiments are cited properly.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: No new assets are released with this submission.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: This paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: This paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.Just like in undirected graphical models, the different types of inference are well-defined despite lack of normalization. Table1shows the precise definitions including two reasonable definitions of marginalization.We assume familiarity with variational inference, see(Jordan et al., 1999) for an introduction.In this work we will use the standard VI notation for expectation, where E q(x)[•] is written as ⟨•⟩ q(x) .Two types of marginal inference are included for precision. "Marginal" refers to marginal inference directly applied on the same exact factor graph as the other types of inference. Because the factor graph lacks a prior over a, it is not a properly normalized joint distribution. Adding a uniform prior over the actions resolves this and results in "Marginal U ". Both are a constant apart and are of independent interest.Code at https://github.com/google-deepmind/what_type_of_inference_is_planning.Setting λ = 0 can result in degeneracy problems, so we use a small value instead, see Appendix H.3. 
 
 Appendix:  


Decision: The paper proposes a framework for establishing a correspondence between various inference queries in graphical models and planning in MDPs. The paper relies on variational inference approach to inference in graphical models, and unifies inference for planning with other type of queries. The theoretical results are confirmed by empirical evaluation on several domains.

While all or at least most reviewers welcomed the insights provided by the paper, most also pointed at lack of clarity of the presentation, as well as at the lack of rigor in definitions and theoretical analysis. Some of the concerns were addressed in the discussion between the authors and the reviewers, while others, in particular clarity of exposition and rigor of definitions, still stand. The reviewers conditioned their evaluations on improved clarity and less dependence on external background.

Based on the reviews and the discussions, I recommend accepting the paper for spotlight presentation . I believe that spotlight presentation strikes the right balance between exposure of the paper to the audience, and the need for more detailed and interactive discussion of paper details than a full-length oral presentation would provide.

Reviews: review: paper_summary: paper_summary: The paper proposes a framework to understand, as the title suggests, what type of inference is (probabilistic) planning. The authors make use of variational inference which encompasses marginal, MAP, and marginal MAP (MMAP) inference to theoretically compare the power of such types of inference in bounding the optimal expected reward for probabilistic planning. Furthermore, the authors propose an approximation of planning inference for factored MDPs as they search space is exponential in the input problem. Experiments are run to support the theoretical results and claims.
strength_weakness: strength_weakness: 1. The main weakness of the paper is its clarity. The paper can be better self-contained if some of the other sections can be better motivated and/or explained by an additional sentence or two, rather than references to the appendix. Furthermore, some of the equations and technical details seem to be ambiguous and not well defined. See suggestions/comments below.
questions: questions: 1. The introduction mentions that planning inference is the same as `value iteration', but nowhere else in the paper is value iteration nor Bellman backups explicitly mentioned. Is this a typo with variational inference (both have the same acronym), or is this intended? If this is intended, please expand on this relationship. The closest looking result is in Sec. 3.3.
2. Can you explain more what is the meaning and/or impact of the result that $F^{\text{planning}}_{\lambda} \leq F^{\text{marginal}}_{\lambda}$? e.g. Is the marginal inference an overapproximation? 
3. What are the terms in the denominator of $H_{\text{MDP}}$ and how is it computed for the IPPC domains?

Suggestions/comments
- It would be helpful for the reader to provide definitions of some notation in the variational inference section. More specifically it would be helpful to define what is a factor graph and the function $\langle \cdot \rangle_{q}$ in the `energy term'.
- It could be worth mentioning what is the type of $\mathbf{a}$ and $\mathbf{x}$ in Eqn. 1. I assume now that it is a list of $a$s and $x$s of size $T$
- line 114: never access to the full joint -> never access the full joint
- The motivation and explaination for the Bethe approximation can be brought earlier rather than referring to the appendix.
- The term $H_{\text{Bethe}}$ is not used in the equation under line 118. I only see $H_{\text{Bethe}}^{\text{planning}}$ and $H_{\text{Bethe}}^{\text{marginal}}$
- Sec 3.3. forward updates: the sum should not range over $a_t$ if it is defined as the argmax of $Q(x_t, a_t')$. Furthermore, either bring the equality out of the equations, or remove the $a_t=$s in the forward updates and posterior equations.
- The meaning of $H_{\text{MDP}}$ as normalised entropies can be explained with an additional sentence rather than referring to the appendix. Furthermore, even when looking at the appendix, none of the $N_e, N_a, N_s$ terms seem to be defined anywhere in the paper. Also is this a new metric or something that exists? There does not seem to be a reference associated with it.
limitations: limitations: The authors correctly fill in the checklist and justify their answers.
paper_summary: paper_summary: This paper shows that planning in an MDP can be posed as a specific form of
inference in a graphical model; in this context of inference, different forms
of inference can be applied, with different results. Additionally, alternate
forms of inference such as variational techniques can be used, which allow
better plans to be inferred than existing baselines. 

This is not a perfect paper, but overall it is a good idea, well executed and
I recommend it for acceptance.
strength_weakness: strength_weakness: The paper has two primary weaknesses:

- There is no discussions of the weaknesses of the inference-based
  technique. It is not clear if the VBP is computationally more costly than,
  for instance, the gradient-based SOGBOFA techniques. Timing information
  would have been very helpful.

  It is also the case that while VBP consistently matches the best performing
  baseline, it does not seem to outperform any of the baselines. It would have
  been helpful to know why VBP isn't able to match the exact planning
  technique -- where is the loss in performance coming from?

- Some of the writing is less than clear. For instance, the exponential
  utility is introduced in table 1, and is justified on page 3 with a short
  reference to being "more suitable for a factor graph representation" but
  more explanation would have been helpful. Please note in the author response
  that the concern is not that the exponential utility is problematic, but the
  text needs to spend more time addressing and justifying this.

  Similarly, the introduction of the $\lambda$ risk setting is not the common
  case, and needs more justification. It's not clear that the $\lambda$ term
  adds much to the primary point of the paper, and seems to be set to 0 for
  most (if not all) of the experimental results. Furthermore, appendix F.3.7
  indicates that $\lambda$ has no meaning if "if the reward can have arbitrary
  scaling". This is a crucial point that should be in the main body of the
  paper, and in fact the paper might be clearer without incorporating
  $\lambda$ at all since it does not add much to the explanation of planning
  as inference.
questions: questions: - Are there any computational constraints on the VBP? Is it comparable in
  speed to the gradient descent techniques?

- Are there convergence issues? The paper briefly discusses this but more
  detail is needed.

- Can the other forms of inference (e.g., $F^{marginal}$, etc.) map exactly to
  different forms of planning? The experimental results seem to suggest this,
  e.g., $F^{marginal}$ maps to ARollout, but it would be helpful to know this
  earlier in the paper.
limitations: limitations: The authors did not include a discussion of limitations, and this is one of the
weaknesses of the paper.
paper_summary: paper_summary: This work introduces a variational inference (VI) framework to characterise different types of inference for planning, specifically for finite-horizon MDPs represented as probabilistic graphical models. They also develop an inference algorithm (VBP) that takes inspiration from the loopy belief propagation and adapts it to planning. An experimental evaluation seems to confirm the theoretical analysis.
strength_weakness: strength_weakness: The paper has two major flaws. First, the text is poorly written, and it definitely doesn’t meet the standards of a high profile conference as NeurIPS. In particular,
 
1) The introduction and the first subsection of the backgrounds have zero references.

2) The paper is not self-contained. I understand the limit of space, but the background section doesn’t provide all the necessary background. Moreover, the experiment on “Reactivity avoidance” is interesting, but most of the explanation is in the appendix, making it hard to grasp with the sole information in the paper.
3) The notation is not always properly introduced, for example:

 - At the beginning of 2.2 I would explicitly write the equations for the different types of inference. Considering how central they are to the paper, and the fact that the work if theoretical, I would expect a more formal definition.
 
- The risk parameter \lambda is introduced in section 3 without any context on what that means in terms of planning. It is not in the standard formulation of MDPs, nor introduced in your background section.

- The “discussion” is not really a discussion, maybe we can call it a conclusion, but anyway it looks rushed and not very “conclusive”
See detailed comments below for more examples.

Second, the soundness of the contribution is undermined by missing details and not very convincing results. In particular:

4) Your definition of “planning inference”, that is central to the paper, is too fuzzy. On line 96 you state that your definition of “planning inference” corresponds to the entropy in Eq.4, however later on line 181, you state that your definition of inference is exact. This I think is a bit confusing. VI is by nature an approximation. I presume I understand what you want to say, nevertheless I think it should be clarified.

5) The discussion on the different types of inference lacks rigour. The notation is not always clear, and most importantly, it is not clear what is the impact of this finding on the planning community. What does it mean in practice that “planning inference” is different from all the others in stochastic settings?

6) The experiments, despite being extensive, don’t show a significant impact coming from the new “planning inference” introduced by the authors. See my questions to the authors for more details.
questions: questions: 1) Why do you focus on finite-horizon MDPs? Do your result easily translate to infinite-horizon MDPs?
2) In the introduction (line 27) you mention value iteration, but then any connection with classic MDP algorithms (and Bellman update) is missing. Moreover, you focus on “best exponential utility”, why not the classic “maximum expected utility”? Can you elaborate on this? I think there is a sort-of hint on this in section 3.3 but it is not exactly clear to me.
3) In Figure 2 (right) the x-axis should be in [0,1] if you are plotting the normalized entropy, why is it not the case?
4) Connected to the previous question, how do you explain the fact that the different methods converge again when the stochasticity increases? From 4.2 you seem to suggest that the more stochastic the environment, the more your solution should be preferable. Am I missing something?
5) In Figure 3, it looks like SOGBOFA-LC performs slightly worse on game of life than sysadmin. Doesn’t it go against the intuition that MMAP should degrade when the stochasticity increases?
6) On line 276 you say that you notice a *significant* advantage of your proposal wrt to SOGBOFA-LC. I’m not sure if I agree with it. Only for the game of life there is clear improvement, but in that case a Rollout is performing better. Can you elaborate on this?



Minor comments:

- In the abstract, the sentence “...show that all commonly used types of inference correspond to different weightings of the entropy terms” is a bit misleading since these are already known results, as you point out in section 2.2. I recommend re-writing in order to not set the wrong expectations to the reader.

- Some notation is not properly introduced: line 62 (angular brackets, I assume it’s a shorthand for the expected value that might be standard in VI but not in planning communities), line 82 (the limit), line 158 (n_a, n_s), etc.

- Line 44, “small subset of x_t” is an assumption. In principle, x_t^(i) can depend on all x_t-1

- Line 64, I think the “-” before the log shouldn’t be there

- Better avoid contractions and other “informal abbreviations” e.g. “let’s” (line 50) or “wrt” (line 176)

- Line 289, “further the understanding”, I think you want to remove that “the”

- a few more words on the “planning as learning” on line 210, and how that is different from your analysis could be interesting.

- There is a lot of math (that I appreciate) but some intuitive explanation could very much improve the presentation of the results.
limitations: limitations: Okay.
paper_summary: paper_summary: This paper investigates the concept of "planning as inference", which frames planning problems (i.e. coming up with actions to reach a goal or attain reward) using the vocabulary and mathematics of probabilistic inference. The paper surveys existing formalizations of this broad concept, finding that none of them exactly correspond to the standard planning notion of computing a policy that maximizes expected cumulative reward. In response, the authors introduce a new variational objective, $F_\text{planning}(q)$ the optimization of which is a generalization of the objective of maximizing expected cumulative reward using some (potentially reactive) policy $\pi$ (instead of just finding a single action sequence $\mathbf{a}$ that performs this maximization, as in MMAP). They also show that this objective differs from existing inference objectives (MAP, MMAP, and Marginal inference) in terms of the entropy terms associated with their variational formulations. The authors then derive several practical methods for optimizing $F_\text{planning}(q)$ based on linear programming (VI LP) or loopy belief propagation (VBP) to compute the optimal $q$ (which corresponds to the action policy $\pi$). In both synthetic experiments and benchmark IPC problems, they show that these methods are competitive with other planning-as-inference algorithms based on other inference formulations, and confirm that optimizing $F_\text{planning}(q)$ leads to (desirably) different properties than MAP or MMAP inference, e.g. in terms of policy reactivity.
strength_weakness: strength_weakness: In my opinion, the main way this paper could be improved is in exposition, especially for a broader audience than people already familiar with planning-as-inference, factor graphs, and variational inference. The introduction right now is very short, and then paper goes straight into mathematical background. IMO, some of the discussion in the Related Work should be moved into the Introduction itself, and I think the Related Work probably is best placed after the Introduction. I also think both the Abstract and the Introduction could foreground the intuitive / standard notion of planning as "maximizing expected cumulative reward", and communicate that their variational formulation of planning-as-inference both reproduces this objective and generalizes it, whereas other inference objectives do not. This, to me, is one of the main upshots of the paper, and it should be communicated clearly from to get-go as a motivation. Right now, the idea that maximizing $F_\text{planning}(q)$ generalizes "maximize expected cumulative reward" only starts appearing in Table 1, and  Section 3.1.

As an additional organizational suggestion, after introducing the Background, I think it is probably better to cover the content in Section 4 first, by introducing $F_\text{planning}(q)$ as a variational objective, then comparing it to the other existing inference objectives. After you have established that $F_\text{planning}(q)$ is the "right" objective for planning, then you can go into the content of Section 3.2 as a separate section that is focused on practical methods for optimizing the planning objective. By organizing things in this way, you first clearly motivate the desirability of $F_\text{planning}(q)$ as an objective, which then motivates practical methods for optimizing $F_\text{planning}(q)$.

Aside from exposition, I think a number of theoretical claims that the paper makes could be better explained and clarified. In particular, it was not obvious to me that the ranking of inference types in Section 4.1 could be read off from the entropy terms in Table 1 -- there should be an associated proof in either the main paper or Appendix. There are also a few notational choices that I think need to be clearly defined before use, and several sentence discussing the relationship of  $F_\text{planning}(q)$ to other inference objectives that could be clarified. I will detail these more in the Questions section.

I think the experiments could be made even stronger by comparing against e.g. Monte Carlo methods for planning-as-inference (e.g. Piche et al. (2018)) and model-based planning algorithms for MDPs (standard value iteration, RTDP, etc.), but this is not strictly necessary.
questions: questions: Line 62: "For a general factor graph f(x, a)" -- please define what f(x, a) is. Even among probabilistic inference practitioners, the factor graph representation of a inference problem may not be widely known (compared to e.g. computing or sampling from a posterior distribution).

Line 62: I think the bra-ket notation for expectations should probably be defined somewhere, since it is less commonly used than the expectation operator. And perhaps the paper should consistently use one notation or the other.

Table 1: Could you provide derivations or explanations of the variational identities for Marginal, MMAP, and MAP somewhere (e.g. the Appendix), just as you've done for $F_\text{planning}(q)$? Right now it's not obvious to me why the conditional entropies end up differing in the way shown in column 2, and it seems like there should be some fairly straightforward intuition as to why, e.g. MMAP requires subtracting out $H_q(a_t)$, and why Marginal has $H_q(x_{t+1}, a_t | x_t)$ instead of $H_q(x_{t+1} | a_t, x_t)$ as the conditional entropy term.

Table 1 and Eq 1: $R(\mathbf{x}, \mathbf{a})$ should be explicitly defined some where as the cumulative reward.

Line 159: Some derivation of the computational complexity would be good (e.g. in the Appendix).

Lines 180-181: "none of which corresponds with the exact “planning inference” from this work, which is exact." --- exact with respect to what? Exactly captures the notion of maximizing expected cumulative reward? Exact in the sense that $F_\text{planning}$ is not a lower bound of itself? I think this should be clarified.

Line 182: "First, from inspection of the entropy terms it is trivial to see that.." --- to me this wasn't trivial for all the comparisons shown, and there should be some explanation and derivation. In particular, it was not obvious to me why the entropy term for Marginal$^\text{U}$ should be lower the entropy term for MAP, which is zero.

Lines 185-186: "Since the tightness of a lower bound is an indication of its quality, it follows that MMAP inference is no worse and potentially better than all other common types of inference." --- I think it is confusing for this sentence to follow right after Equation (8), because it suggests that the "best" objective is $F_\text{marginal}$, even though the whole point of the paper is that  $F_\text{marginal}$ does not capture our standard notion of planning. I think it should be clarified that the MMAP objective is a lower bound to the planning objective in particular, which is the true objective the paper cares about. You could do this with a sentence like "Except for $F_\text{marginal}$, which is not a planning objective in the sense of maximizing expected (exponential) utility,  $F_\text{MMAP}$ is the best lower bound to  $F_\text{planning}$".
limitations: limitations: While there is no explicit limitations section, the authors adequately discuss the approximate nature of their proposed optimization methods, and also discuss cases where their proposed objective is equivalent (and hence does not improve on) existing planning-as-inference formulations (namely, cases without deterministic dynamics).

There is some discussion of this already, but I think it would be good for the paper to better recognize when Marginal$^\text{U}$ might be desirable as an objective, as this corresponds to a notion of "soft planning" that is similar to Boltzmann-rational models of action selection and max-entropy inverse RL (Ziebart et al, 2010). Sometimes, our goal is not to derive a reward-optimal policy, but to get a policy that is stochastic (because we desire diversity, or because we want to model human planning).

The paper is largely theoretical in nature, and discussions of societal impact are not immediately relevant.
paper_summary: paper_summary: This paper studies 3 types of factor graph inference for planning and in particular their relationship to optimal planning. The well known $\exp(\lambda R(x, a, x'))$ factor is used. MAP inference computes the maximum energy configuration over states and actions which corresponds to zero posterior entropy. Marginal inference computes the joint over states and actions. Marginal MAP inference set the action entropy in marginal inference to zero. An interesting connection was made with the dual LP formulation of MDP. The method was further applied to factored state MDP. The relationship between MDP stochasticity and inference approximation to optimal planning was studied in the experiments.
strength_weakness: strength_weakness: There isn't any salient weaknesses of the paper as far as I can tell. My impression is the results are somewhat "expected" given this type of "planning as inference" has been widely studied in prior work, at least empirically. 

One thing that would be of interest is how "reactivity" interacts with online re-planning.
questions: questions: I don't have any outstanding questions for the authors.
limitations: limitations: This paper does not contain a limitations section.

Comments: title: Thank you for the response.
comment: Thank you for the response, and for the explanation of the sequential bounding in particular, which clarified my confusions. Do include these derivations in the Appendix.

Regarding derivations of the variational expressions, I think it's up to the authors to include the full derivations in the Appendix, but I do think readers will probably find it helpful if some explanation or intuition is provided. For Marginal$^U$ inference, for example, I can see that the $H(q)$ term is really just some kind of KL-divergence between $q(x, a)$ and the (uniform) prior over trajectories or actions. For MAP, I can also see the intuition for why $H(q)$ is zero, because in MAP inference you are just interested in finding a point estimate, and so $q$ should have zero uncertainty (and hence zero entropy). For MMAP, it was helpful for me to realize the entropy term is just equal to $H_q(x_{1:t}, a_{1:t}) - H_q(a_{1:t}) = H_q(x_{1:t} | a_{1:t})$, which intuitively makes sense because in MMAP, you only want to marginalize over $x_{1:t}$ for a fixed value of $a_{1:t}$, and hence only care about the randomness in $x_{1:t}$ conditional on $a_{1:t}$. I think these sorts of intuitive explanations would be helpful to include somewhere.

I'll be keeping my score of 7. I encourage the authors to restructure the exposition of their paper in some of the ways I suggested, so that the paper will be more accessible to others and have a greater impact.
I thank the authors for their detailed rebuttal and will increase my score to a weak accept.
I hope the authors can take some of the criticism into account when preparing the camera ready version.
I thank the authors for their clear rebuttal. I have no further questions.
I thank the author for their response and clarifications. I have no further questions.
I thank the authors for the response. The worked example is very helpful.
**The introduction and the first subsection of the backgrounds have zero references.**

This work is related to a vast amount of literature from classical planning, reinforcement learning, variational inference, influence diagrams, etc. While it is impossible to cite all the related work, we have included a selection in our Section 5, "Related work", trying to at least touch all relevant subfields.
We already have on our radar some additional citations that we want to include in the final version and are happy to hear suggestions for any glaring missing citations.

The reason why all citations from the introduction have been moved Section 5 is that we wanted to be able to connect each citation with a type of inference, and potentially discuss other details about it in relation with our VI framework, and this was only possible after developing the theory sections of this paper.

We will add MDP references to Section 2.1.

**The paper is not self-contained. I understand the limit of space, but the background section doesn’t provide all the necessary background.**

As mentioned before, this work connects multiple fields, so detailed background about all of them cannot be included. Some degree of familiarity with factor graphs, variational inference, loopy BP, and reinforcement learning does indeed help with the reading. We have included the minimal background required to be able to derive our results from either first principles or cited sources. While we are unlikely to be able to fit much more information in the background section, we would like to know if the reviewer has a particular result in mind that could be cited or included to make this work more self-contained.

**The notation is not always properly introduced, for example:**

**(a) Explicitly write the equations for the different types of inference (...) I would expect a more formal definition** 

The explicit expression for each type of inference appears in the second column of Table 1. This is a precise definition of each type of inference on the factor graph of Figure 1[Left]. 

**(b) The risk parameter $\lambda$ is introduced in section 3 without any context on what that means in terms of planning. It is not in the standard formulation of MDPs, nor introduced in your background section.**

Section 3 has three references (Marthe et al., 2023; Föllmer and Schied, 2011; Shen et al., 2014) that explain the role of $\lambda$ in planning. It controls how risk-seeking the agent is. Although this is not standard in MDPs or RL, it is not a concept that we introduce in this paper, but rather, a concept that has already been developed for planning in MDPs and that we leverage to include both the dynamics and the rewards within the same factor graph, since all the terms become multiplicative in this formulation. This is a generalization of the standard utility in MDPs, so we do not lose generality.

**(c) Your definition of “planning inference”, that is central to the paper, is too fuzzy** 

Theorem 1 defines the "planning inference" objective, which is Eq. (2), whose terms are further defined in Eqs. (3) and (4). Approximations are introduced in Section 3.2 to make this objective tractable for factored MDPs.

**You state that your definition of inference is exact. This I think is a bit confusing. VI is by nature an approximation.** 

To clarify: VI is exact when the variational distribution is arbitrarily flexible and is optimized completely. In other words, the evidence lower bound (ELBO) matches the exact evidence if (a) the variational distribution can fit the posterior arbitrarily well and (b) the optimization finds the maximum of the ELBO. VI is thought of as approximate because typically none of these two conditions are met. In the case of a standard tractable MDP, both conditions are met for "planning inference", and it produces the exact result. This makes sense, since other techniques (such as value iteration) also allow for exact planning. In the case of an intractable factored MDP, we need to introduce approximations, and the proposed VBP no longer corresponds to exact planning.