Corollary 1: Let be an action theory. Then, can be directly encoded as a SAT formula S where the models of S
are equivalent to valid trajectories in .

VIII. CONCLUSIONS AND RELATED WORK
We described a new high level action language, , that allows the factored representation of POMDP. Moreover, we presented a new reinforcement learning framework by relating reinforcement learning in POMDP to NHPLP. The translation from an action theory representation of a reinforcement learning problem in into an NHPLP program is based on a similar translation from probabilistic planning into NHPLP [28]. The difference between and the action languages 
[1], [2], [5], [11], and [17] is that is a hight level language and allows the factored specification of POMDP.

 The approaches for solving POMDP to find the optimal policies can be categorized into two main approaches; dynamic programming approaches and the search-based approaches (a detailed survey on these approaches can be found in [2]). However, dynamic programming approaches use primitive domain knowledge representation. Moreover, the search-based approaches mainly rely on search heuristics which have limited knowledge representation capabilities to represent and use domain-specific knowledge.

In [22], a logical approach for solving POMDP, for probabilistic contingent planning, has been presented which converts a POMDP specification of a probabilistic contingent planning problem into a stochastic satisfiability problem and solving the stochastic satisfiability problem instead. Our approach is similar in spirit to [22] in the sense that both approaches are logic based approaches. However, it has been shown in [29] that NHPLP is more expressive than stochastic satisfiability from the knowledge representation point of view. In [15], based on first-order logic programs without nonmonotonic negation, a first-order logic representation of MDP has been described. Similar to the first-order representation of MDP in [15], AMD allows objects and relations. However, unlike APO, [15] finds policies in the abstract level. But, NHPLP allows objects and relations. [3] presented a more expressive first-order representation of MDP 
than [15] that is a probabilistic extension to Reiter's situation calculus. However, it is more complex than [15].

## References

Artificial *Intelligence*, 2000.

[7] M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. *ICSLP*, 1988, MIT Press. 

[8] M. Gelfond and V. Lifschitz. Classical negation in logic programs and disjunctive databases. *New Generation Computing*, 9(3-4):363385, 1991. 

[9] M. Gelfond and V. Lifschitz Representing action and change by logic programs. *Journal of Logic Programming*, 17:301–321, 1993. 

[10]. S. Holldobler, E. Karabaev, and O. Skvortsova. FluCap: A heuristic search planner for first-order MDPs. *JAIR*, 27:419–439, 2006. 

[11] L. Iocchi, T. Lukasiewicz, D. Nardi, and R. Rosati. Reasoning about actions with sensing under qualitative and probabilistic uncertainty. In 16th European Conference on Artificial Intelligence , 2004.

[12]L. Kaelbling, M. Littman, and A. Cassandra. Planning and acting in partially observable stochastic domains. *Artificial Intelligence* , 101: 99-134, 1998. 

[13]L. Kaelbling, M. Littman, and A. Moore. Reinforcement Learning: A 
Survey. *Journal of Artificial Intelligence Research* , 4:237-285, 1996. 

[14]H. Kautz and B. Selman. Pushing the envelope: planning, propositional logic, and stochastic search. In 13th National Conference on Artificial *Intelligence*, 1996.

[15]K. Kersting and L. De Raedt. Logical Markov decision programs and the convergence of logical TD(λ). In *14th International Conference* on *Inductive Logic Programming*, 2004.

[16]K. Kersting, M. van Ottterlo, and L. De Raedt. Bellman goes relational. In *ICML*, 2004. 

[17]N. Kushmerick, S. Hanks, and D. Weld. An algorithm for probabilistic planning. *Artificial Intelligence* , 76(1-2):239-286, 1995. 

[18] V. Lifschitz. Answer set planning. In *ICLP*, 1999. [19]F. Lin and Y. Zhao. ASSAT: Computing answer sets of a logic program by SAT solvers. *Artificial Intelligence* , 157(1-2):115-137, 2004. 

[20]M. Littman, A. Cassandra, and L. Kaelbling. Learning policies for partially observable environments: scaling up. In *12th ICML*, 1995. 

[21]S. Majercik and M. Littman. MAXPLAN: A new approach to probabilistic planning. In 4th International Conference on Artificial Intelligence *Planning*, pages 86–93, 1998.

[22]S. Majercik and M. Littman. Contingent planning under uncertainty via stochastic satisfiability. *Artificial Intelligence* , 147(1–2):119–
162, 2003. 

[23]M. Mundhenk, J. Goldsmith, C. Lusena, and E. Allender. 

Complexity of finite-horizon Markov decision process problems. Journal of the ACM, 2000. 

[24]I. Niemela and P. Simons. Efficient implementation of the wellfounded and stable model semantics. *In Joint International* Conference and *Symposium on Logic Programming*, 289-303, 1996.

[25] E. Saad. Incomplete knowlege in hybrid probabilistic logic programs. 

In 10th European Conference on Logics in Artificial Intelligence , 2006.

[26]E. Saad. Towards the computation of the stable probabilistic model semantics. In 29th Annual German Conference on Artificial Intelligence , June 2006. 

[27]E. Saad. A logical approach to qualitative and quantitative reasoning. 

In 9th European Conference on Symbolic and Quantitative Approaches *to Reasoning with Uncertainty*, 2007.

[28]E. Saad. Probabilistic planning in hybrid probabilistic logic programs. In 1st International Conference on Scalable Uncertainty Management, 2007. 

[29]E. Saad On the relationship between hybrid probabilistic logic programs and stochastic satisfiability. In *10th International* Symposium on Artificial *Intelligence and Mathematics*, 2008.

[30]E. Saad. A logical framework to reinforcement learning using hybrid probabilistic logic programs. In *Proceedings of the 2nd International* Conference on Scalable Uncertainty Management (SUM'08), 2008.

[31]E. Saad. Probabilistic planning with imperfect sensing actions using hybrid probabilistic logic programs. In SUM, 2009. 

[32]E. Saad. Probabilistic reasoning by SAT solvers. In *Tenth* ECSQARU, 2009. 

[33]E. Saad and E. Pontelli. Towards a more practical hybrid probabilistic logic programming framework. In *Practical Aspects of* Declarative *Languages*, 2005.

[34]E. Saad and E. Pontelli. A new approach to hybrid probabilistic logic 