{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T10:30:39Z","timestamp":1768559439788,"version":"3.49.0"},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Patt. Recogn. Artif. Intell."],"published-print":{"date-parts":[[1999,11]]},"abstract":"<jats:p> In this paper, we address the tradeoff between exploration and exploitation for agents which need to learn more about the structure of their environment in order to perform more effectively. For example, a software agent operating on the World Wide Web may need to learn which sites on the net are most useful, and the most efficient routes to those sites. We compare exploration strategies for a repeated task, where the agent is given some particular task to perform some number of times. Tasks are modeled as navigation on a partially known (deterministic) graph. This paper describes a new utility-based exploration algorithm for repeated tasks which interleaves exploration with task performance. The method takes into account both the costs and the potential benefits (for future task repetitions) of different exploratory actions. Exploration is performed in a greedy fashion, with the locally optimal exploratory action performed during repetition of each task. We experimentally evaluated our utility-based interleaved exploration algorithm against a heuristic search algorithm for exploration before task performance (a priori exploration) as well as a randomized interleaved exploration algorithm. We found that for a single repeated task, utility-based interleaved exploration consistently outperforms the alternatives, unless the number of task repetitions is very high. In addition, we extended the algorithms for the case of multiple repeated tasks, where the agent has a different, randomly-chosen task (from a known subset of possible tasks) to perform each time. Here too, we found that utility-based interleaved exploration is clear in most cases. <\/jats:p>","DOI":"10.1142\/s0218001499000537","type":"journal-article","created":{"date-parts":[[2003,4,24]],"date-time":"2003-04-24T01:59:35Z","timestamp":1051149575000},"page":"963-986","source":"Crossref","is-referenced-by-count":1,"title":["INTERLEAVED VERSUS <i>A PRIORI<\/i> EXPLORATION FOR REPEATED NAVIGATION IN A PARTIALLY-KNOWN GRAPH"],"prefix":"10.1142","volume":"13","author":[{"given":"SHLOMO","family":"ARGAMON-ENGELSON","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, Bar-Ilan University, 52900 Ramat Gan, Israel"},{"name":"Department of Computer Science, Jerusalem College of Technology, P.O.B. 16031, 91160 Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SARIT","family":"KRAUS","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Bar-Ilan University, 52900 Ramat Gan, Israel"},{"name":"Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SIGALIT","family":"SINA","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Bar-Ilan University, 52900 Ramat Gan, Israel"},{"name":"Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"p_1","first-page":"416","author":"Albers S.","year":"1997","journal-title":"Proc. 29th Annual ACM Symp. Theory of Computing"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00014-9"},{"key":"p_8","first-page":"3","volume":"18","author":"Betke M.","year":"1995","journal-title":"Mach. Learn."},{"key":"p_9","first-page":"2","author":"Blum A.","year":"1993","journal-title":"Proc. Symp. Foundations of Computer Science"},{"key":"p_11","first-page":"1347","author":"Chimura F.","year":"1994","journal-title":"Proc. National Conf. Artificial Intelligence"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001496000281"},{"key":"p_13","first-page":"1","volume":"18","author":"Dean T.","year":"1995","journal-title":"Mach. Learn."},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)00086-G"},{"key":"p_16","first-page":"9","volume":"4","author":"Etzioni O.","year":"1991","journal-title":"Artif. Intell."},{"key":"p_17","first-page":"229","author":"Haddawy P.","year":"1995","journal-title":"Proc. Conf. Uncertainty in Artificial Intelligence"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1109\/34.387507"},{"key":"p_19","first-page":"305","author":"Ishida T.","year":"1996","journal-title":"Proc. National Conf. Artificial Intelligence. Portland. OR"},{"key":"p_21","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1613\/jair.301","volume":"4","author":"Kaelbling L. P.","year":"1996","journal-title":"J. Artif. Intell. Res."},{"key":"p_22","first-page":"352","author":"Karakoulas G. I.","year":"1995","journal-title":"Eleventh Annual Conf. Uncertainty in Artificial Intelligence"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(90)90054-4"},{"key":"p_24","first-page":"103","volume":"13","author":"Moore A. W.","year":"1993","journal-title":"Mach. Learn."},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90257-3"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73047"}],"container-title":["International Journal of Pattern Recognition and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218001499000537","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T02:12:13Z","timestamp":1565143933000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218001499000537"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,11]]},"references-count":18,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[1999,11]]}},"alternative-id":["10.1142\/S0218001499000537"],"URL":"https:\/\/doi.org\/10.1142\/s0218001499000537","relation":{},"ISSN":["0218-0014","1793-6381"],"issn-type":[{"value":"0218-0014","type":"print"},{"value":"1793-6381","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,11]]}}}