I'll take a stab at this one.

There is a pervasive but false understanding that the Byzantine, or late Roman Empire only fought defensive wars. That the empire was at such a progressed state of decay that it lacked the ability to mount offensives outside of its borders. While this is true in some periods when the strength of the empire waned, there are just as many periods when the Empire was strong and sought to reclaim what had been lost.

I won't focus on all time periods or all regions when the Empire was strong and on the offensive, but rather, how long they stayed on the offensive in the east, particularly the Levant, in order to more specifically address your question.

One of the most successful periods of late Roman expansion in the east was in the late 10th century under the command of Emperor Nikephoros II Phokas. Nikephoros made many successful incursions into modern day Syria against the Hamdanids, an Arab Caliphate Kingdom present in the region and ruling from Mosul. In the Praecepta militaria written by Nikephoros he gives us a wealth of knowledge and insight on Roman tactics of the time. However, we can also gain understanding of how he viewed the regions he was invading.

On your way through hostile territory you should set fire to the regions and their settlements and burn the dwellings, the crops, and the pastures. In the place where you intend to return and rest the army, however, do not burn the pastures and the grain, but guard these very closely so that the host will find food for itself and the horses.

Note that Nikephoros does not mention attempting to win over the native population, this is hostile territory meant to be conquered, not liberated. These regions had been under Arab Muslim rule for almost 300 years at this point, and even prior to that the Christian population of the Levant and Africa was primarily Monophysite and largely hostile to Roman (Orthodox Christian) rule.

Nikephoros also mentions the following regarding sieges,

For the enemy, oppressed by lack of provisions, send to the inner regions of Syria and to the towns and communities, and proclaim to the faithful in the mosques and calamities which have befallen them and the pain of starvation oppressing them. They tell them such things as, should our fortress fall into the hands of the Romans, it will be the ruin of all the lands of the Saracens," whereupon the Saracens rise to the defense of their brethren and their faith.

Again we see the Nikephoros views the entire population as hostile, not former Roman subjects waiting for salvation. Despite this, Nikephoros still desires to conquer these lands. We don't know whether this is due to some attempt to restore the former borders of the Empire, or merely adjacent territory that was vulnerable.

The Hamdanid Caliph Emir, Sayf al-Dawla, lost dominions relentlessly before the continuous waves of Roman invaders who isolated and captured the principal strongholds of Cilicia (Adana, Mopsuestia, and Tarsos) and then went on to seize control of northern Syria. In his 966 campaign Nikephoros' armies moved unmolested between Aleppo and Antioch, showing the weak state of Hamdanid resistance. Nikephoros rebuffed Sayf al Dawla's desperate offer of tribute by naming half of Syria as his price for a truce. The death of the Hamdanid Caliph Emir the next year was followed by the fall of Antioch in 969 and vassalization of his kingdom to the Romans.

The next period of Roman expansion was performed under Basil II who died in 1025. Basil's primary focus was westward (how he earned his name "The Bulgar Slayer"), and at the time of his death, the Empire was in an extremely strong position. While geographically smaller than during Justinian's reign, the empire was compact and not spread out over distant and indefensible holding across the Mediterranean. Where Justinian was dealing with internal religions conflict, Basil's Empire was united under one cohesive faith. Where Justinian had to contend with a strong and confrontational Sassanian empire in the east, Basil's reign saw a weak Buyid dynasty struggling with internal religious strife. Unfortunately for Basil's successors, a new thread burst from the east in the form of newly converted horsemen from the Turkic clans. The Turkic clans coalesced into what we remember them as today, the Seljuks. Not even a coherent power in 1025, within thirty years they had carved out a vast kingdom containing much of modern day Iraq, Iran and Uzbekistan. Seljuk and Roman forces collided at Mantzikert in 1071, leading to a crushing Roman defeat and almost completely undoing the gains of the previous one hundred years.

After Basil, the next expansion comes during the Komnenian restoration, starting with Alexios I Komnenos who came to power in 1081. In 1095 Alexios sent his ambassadors to Pope Urban II at the Council of Piacenza, leading to the First (and subsequent) Crusades. Several of Alexios' goals are clear as laid out in the Alexiad. He is focused on recovering former Roman lands to the empire, and has the Crusaders swear oaths to do so.

On the Oath:

In consequence Godfrey shortly afterwards yielded to the Emperor's wish. He went to the Emperor and swore the oath which was required of him, namely, that whatever towns, countries or forts he managed to take which had formerly belonged to the Roman Empire, he would deliver up to the Governor expressly sent by the Emperor for this purpose

Intentions of the Crusaders:

As [Bohemund] did not wish to cede Antioch to Taticius according to the oath he had previously sworn to the Emperor, but rather longed for it for himself, Bohemund planned a wicked plan which would force Taticius to remove himself from the city against his will.

Alexios Learning of the Crusader's deceptions:

Soon the Emperor learnt of the seizure of Laodicea by Tancred, and therefore sent a letter to Bohemund which ran as follows: "You know the oaths and promises which not only you but all the Counts took to the Roman Empire. Now you were the first to break them, by retaining possession of Antioch, and then taking more fortresses and even Laodicea itself. Therefore withdraw from Antioch and all the other cities and do what is just and right, and do not provoke more wars and troubles for yourself."

The result of the First 3 crusades was mixed but did allow the Romans to recover many lost parts of Anatolia.

The last attempt to recapture lost Asian territory was Manuel I's attempt to recapture the interior of the Anatolia. In 1176, Manuel led his forces to strike the Seljuk capitol of Iconium (in central Turkey). Manuel's forces were moving through a mountain pass on September 17, 1176 when they were ambushed by the Seljuks and defeated decisively. This battle is known as the battle of Myriokephalon, or "ten thousand peaks". While the defeat was not as severe as that suffered in 1071 at Mantzikert, this sapped all initiative from the Roman forces. The situation eventually worsened until the sack of Constantinople in 1204 which ended effective Roman rule. While the empire had been able to recover from calamities before, the loss and sacking of Constantinople proved too great. Although the fall of Constantinople would not come for more than two hundred years, those who still called themselves Roman would exist only in the shadows of their former greatness.

Based on this, it is my opinion that the Byzantine or Romans as they called themselves never gave up trying to reconquer the lost territory of the Empire. Whenever the empire had the strength to do so, they moved against those who occupied their lost lands. However, they may have considered the territory of Africa and the Levant lost to the Arabs in terms of religion and culture, knowing that they would arrive as conquerors and not liberators.

Sources:

Praecepta militaria Nikephoros II Phokas

Taktika Nikephoros Ouranos

Alexiad Anna Komnene

Sowing the Dragon's Teeth Eric McGeer

The Grand Strategy of the Byzantine Empire Edward N. Luttwack

Edit for formatting

Second edit to correct Hamdanid Caliph to Emir